帶拒絕和到達(dá)時(shí)間的單機(jī)排序問題

慕 迪, 劉培海

(華東理工大學(xué)數(shù)學(xué)系,上海 200237)

帶拒絕和到達(dá)時(shí)間的單機(jī)排序問題

慕 迪, 劉培海

(華東理工大學(xué)數(shù)學(xué)系,上海 200237)

研究了一個(gè)單機(jī)帶拒絕的排序問題,目標(biāo)函數(shù)是最小化接受工件的最大完工時(shí)間與所有被拒絕工件的拒絕費(fèi)用之和。首先給出了此問題的混合整數(shù)規(guī)劃模型,并得到了最優(yōu)解的一些性質(zhì)。最后給出了一個(gè)分支定界算法,并給出了數(shù)值模擬的結(jié)果。

排序; 單機(jī); 拒絕; 分支定界

1 最優(yōu)解的性質(zhì)

性質(zhì)1若工件ji和工件jj滿足ri≤rj,pi/wi≤1,則

(1) 若在π*中接受工件jj,則工件ji也一定被接受;

(2) 若在π*中拒絕工件ji,則工件jj也一定被拒絕。

證明 (1)假設(shè)在最優(yōu)排序π*中ji被拒絕,并且ji滿足ri≤rj,pi/wi≤1,因?yàn)棣?接受了工件jj,若在Cmax(π*)時(shí)刻開始加工ji,則目標(biāo)函數(shù)值不會(huì)增加,這與π*的最優(yōu)性矛盾,因此ji在π*中也一定被接受;

(2) 同理可證。

性質(zhì)2若工件jj和工件ji滿足:rj≥ri,pj≥pi,wj

(1)若在π*中接受工件jj,則工件ji一定也被接受;

(2)若在π*中拒絕工件ji,則工件jj一定也被拒絕。

(2) 同理可證。

性質(zhì)3若一段序列{jh,jh+1,…,jh+k}(k>0)滿足:?ji∈{jh,jh+1,…,jh+k},pi/wi≤1,工件jh前和jh+k后分別都是一段空閑,且jh和jh+k之間無空閑,則在最優(yōu)時(shí)間表π*中,{jh,jh+1,…,jh+k}總是同時(shí)被接受,或者同時(shí)被拒絕。

證明 若jk被接受,則?ji∈{jh,jh+1,…,jh+k-1},有pi/wi≤1,且顯然有ri≤rk,由性質(zhì)1,ji一定被接受;同理,若工件jh被拒絕,則?jj∈{jh+1,jh+2,…,jh+k}一定也被拒絕。

性質(zhì)4在最優(yōu)時(shí)間表π*中,設(shè)最后加工工件開始加工的時(shí)間為tmax,則?t

(1) 機(jī)器在t時(shí)刻忙碌,即在加工某個(gè)工件;

(2) 任何滿足rj≤t,pj/wj≤1的工件均已完工。

2 目標(biāo)問題的上下界

2.1 整數(shù)規(guī)劃模型

假設(shè)所有工件已經(jīng)按照到達(dá)時(shí)間的先后順序重新編號(hào),即

r1≤r2≤…≤rn:

(1)

(2)

xj∈{0,1},j=1,…,n

(3)

其中,

Cmax為最大完工時(shí)間;W為所有被拒絕工件的拒絕費(fèi)用和;M為一個(gè)足夠大的數(shù)。

目標(biāo)函數(shù)為:

minZ=Cmax+W

同時(shí)式(1)保證任何接受工件jj的完工時(shí)間都不大于最大完工時(shí)間,即?jj∈A,且Cj≤Cmax;約束式(2)即求出所有被拒絕工件的懲罰和;式(3)表示工件jj要么被拒絕,要么被加工。

為了更方便地求解此問題,構(gòu)造n個(gè)子問題;在每個(gè)子問題(Pk)中,工件jk必須被接受(即xk=1),而jk之后的工件全部被拒絕。子問題(Pk)的數(shù)學(xué)模型可寫為:

minZk=Cmax,k+Wk

其中Cmax,k、Wk分別表示子問題(Pk)的最大完工時(shí)間和所有拒絕工件的懲罰和。

顯然,這n個(gè)子問題中一定存在某個(gè)問題(Pk)與原問題具有相同的最優(yōu)解。從而對(duì)原問題的求解轉(zhuǎn)換為求解這個(gè)這n個(gè)子問題。而對(duì)于每一個(gè)子問題(Pk),已經(jīng)知道最后接受的工件,這方便了對(duì)問題的求解。

2.2 問題(P)的上下界

(4)

(5)

xj∈[0,1],j=1,…,k-1

(6)

Ak={j|rj≤rk,Pj≤wj};

Bk={j|rj≤rk,Pj>wj}.

(1) ?i∈Ak,xi=1;

由式(4),假設(shè)在某個(gè)最優(yōu)解中

由式(4)可得

(7)

(8)

所以必然有

不妨設(shè)j是使得式(9)成立的最大整數(shù),即

(9)

其中1≤j≤i。

則由式(7),可以得到下面的式子:

從而必然存在某個(gè)y使得iy并且xy>0。那么保持式(9)成立的前提下增大xi至=xi+Δx,同時(shí)減小xy到=xy-Δxpi/py,這樣可以得到松弛問題的一個(gè)新解且目標(biāo)函數(shù)值不增加。

重復(fù)上述過程,總可以找到一個(gè)滿足性質(zhì)3的最優(yōu)解。

例1：考慮一個(gè)4工件排序問題,求解這個(gè)問題的下界。首先將工件重新排序,工件的各項(xiàng)參數(shù)見表1。由于最后接受的工件一定滿足pj/wj≤1(若最后加工的是pj/wj>1的工件,則拒絕這個(gè)工件得到一個(gè)新的時(shí)間表,新時(shí)間表的目標(biāo)函數(shù)值一定比原時(shí)間表小),因此只要考慮k=1,3的情況。

表1 例1中各工件參數(shù)

設(shè)上述算法所得下界UB對(duì)應(yīng)的排序?yàn)棣?,顯然這也是問題(P)的一個(gè)松弛解。

下面討論問題(P)的上界。

對(duì)排序π1進(jìn)行如下處理,得到問題(Pk)的一個(gè)可行排序π2:

步驟1 在排序π1中,

(1) 若(1-xi)pi≤wi,則在π2中令xi=1,即接受工件ji;

(2) 若(1-xi)pi>wi,則在π2中令xi=0,即拒絕工件ji;

步驟2 將所有滿足xi=1的工件按照達(dá)到時(shí)間rj的順序安排加工,拒絕其他工件,得到加工時(shí)間表π2。上述算法得到問題(P)的可行解,將這個(gè)解作為問題(P)的一個(gè)上界。

例2:同樣是例1中的4工件問題,現(xiàn)在求解上界。由例1,xi=1,i=1,3;x2=1/2;x4=0;由于(1-xi)piw4;

則在π2中,令xi=1,i=1,2,3;x4=0;接受工件集合為A={j1,j2,j3},拒絕工件集合為R={j4},計(jì)算得到上界UB=Cmax+w4=8+2=10。

3 分支定界算法

需要先將所有工件按照到達(dá)時(shí)間rj從小到大重新排列,即r1≤r2≤…≤rn。在這里只要考慮拒絕還是接受pj/wj>1的工件,因?yàn)榧庸j/wj≤1的工件不會(huì)使目標(biāo)函數(shù)值增大。利用2.2節(jié)中的方法來計(jì)算各個(gè)節(jié)點(diǎn)處的上下界。在利用分支定界方法進(jìn)行搜索時(shí),定義下述變量:k表示當(dāng)前加工工件集合中到達(dá)時(shí)間最大的工件;UB為問題(P)的一個(gè)上界;UBk表示r*=rk時(shí)的上界;LBk表示r*=rk時(shí)的下界;Sk:表示r*=rk時(shí)的目標(biāo)函數(shù)值,其中S0表示初始解;Opt:最優(yōu)排序的目標(biāo)函數(shù)值。

分支定界算法的主要步驟如下所述:

步驟1 初始化:將Z0=UB作為問題的初始解和初始上界;

步驟2 分支:若LBkUBk,則更新上界UB=UBk;

步驟3 刪除規(guī)則:若在某個(gè)節(jié)點(diǎn)有LBk>UB,則將這個(gè)節(jié)點(diǎn)刪去;

步驟4 停止條件:若已經(jīng)考慮了所有分支,則停止計(jì)算,此時(shí)得到局部最優(yōu)解。

例3:為了更好地說明上述算法,考慮1個(gè)5工件的排序問題。每個(gè)工件的參數(shù)如表2所示。本文得到問題的初始上界S0=16。由于r*∈{rj|pj/wj≤1,j=1,…,5}={r1,r4,r5},因此考慮3種情況,得到的可行解分別為S1=14,S4=13,S5=10;

表2 例3中的各工件參數(shù)

因此,最優(yōu)解為Opt=min{Z1,Z2,Z5}=min{14,13,10}=10;被接受工件集合為A={j1,j2,j4,j5},拒絕工件集合為R={j3}。以r*=r4為例,分支定界過程見圖1。其中,Del表示Delete,即刪除這個(gè)節(jié)點(diǎn)。

圖1 分支定界過程 Fig.1 Procedure of branch-and-bound algorithm

4 數(shù)值模擬

首先利用Cplex軟件對(duì)整數(shù)規(guī)劃模型進(jìn)行求解,并且用C++語言來編譯分支定界算法,為以下參數(shù)的每種組合產(chǎn)生200個(gè)實(shí)例:

(1) 加工工件的個(gè)數(shù)為n∈{50,200,500,1 000};

(2) 工件的到達(dá)時(shí)間、加工時(shí)間和拒絕費(fèi)用分別為[0,100×n×dc],[1,100]和[1,100×rc]上滿足均勻分布的隨機(jī)數(shù),其中dc和rc為控制系數(shù),n為工件個(gè)數(shù);dc∈{0.2,0.5},rc∈{0.5,1,1.5}。用(dc,rc)的形式來表示每種參數(shù)的組合。

表3～表6分別示出了當(dāng)dc∈{0.2,0.5},rc∈{0.5,1,1.5}時(shí),整數(shù)規(guī)劃(IP)的運(yùn)行結(jié)果?？梢钥闯?整數(shù)規(guī)劃模型基本上能得出問題(P)的最優(yōu)解,并且在1 000個(gè)工件內(nèi)效率都比較高,但是運(yùn)行時(shí)間平均比分支定界算法要長(zhǎng)。

表3 n=50時(shí)整數(shù)規(guī)劃運(yùn)行結(jié)果

表4 n=200時(shí)整數(shù)規(guī)劃運(yùn)行結(jié)果

表5 n=500時(shí)整數(shù)規(guī)劃運(yùn)行結(jié)果

表6 n=1 000時(shí)整數(shù)規(guī)劃運(yùn)行結(jié)果

表7 分支定界算法運(yùn)行結(jié)果

本文給出了帶有拒絕工件的單機(jī)排序問題的整數(shù)規(guī)劃模型和分支定界算法。數(shù)值模擬的結(jié)果說明在解決1 000個(gè)工件問題內(nèi),分支定界方法是非常有效的。在以后的工作中,如何把這個(gè)方法推廣到多臺(tái)機(jī)器上將會(huì)是非常值得研究的課題。

符號(hào)說明：

n——工件個(gè)數(shù)

J={j1,j2,…,jn}——工件集合

rj——工件jj的到達(dá)時(shí)間

pj——工件jj的加工時(shí)間

wj——工件jj的拒絕費(fèi)用

Cj——工件jj的完工時(shí)間

R——拒絕工件集合

A——接受工件集合

Z(π)=Cmax(A)+W——時(shí)間表π的目標(biāo)函數(shù)值

[1] BARTA Y,LEONARDI S,MARCHETTI-SPACCAMELA A,etal.Multi-processor scheduling with rejection[J].SIAM Journal on Discrete Mathematics,2000,13(1):64-78.

[2] SEIDEN S S.Preemptive multiprocessor scheduling with rejection[J].Theoretical Computer Science,2001,262(1):437-458.

[3] HOOGEVEEN H,SKUTELLA M,WOEGINGER G J.Preemptive scheduling with rejection[J].Mathematics Programming,2003,94(2-3):361-374.

[4] ENGELS D W,KARGER D,KOLLIOPOULOS S G,etal.Techniques for scheduling with rejection [J].Journal of Algorithms,2003,49(1):175-191.

[5] LU Lingfa,NG C T,ZHNG Liqi.Optimal algorithms for single-machine scheduling with rejection to minimize the makespan[J].International Journal of Production Economics,2011,130(2):153-158.

[6] ZHANG Liqi,LU Lingfa,YUAN Jinjiang.Single machine scheduling with release dates and rejection[J].European Journal of Operational Research,2009,198(3):975-978.

SingleMachineSchedulingwithJobRejectionandReleaseDates

MUDi,LIUPei-hai

(DepartmentofMathematics,EastChinaUniversityofScienceandTechology,Shanghai200237,China)

This paper considers the single machine scheduling problem with job rejection.The objective function is to minimize the sum of the maximum completion time of the job and the rejection lost of all rejected jobs.Firstly,the paper introduces a mixed integer programming model and some properties of the optimal solution.Finally,a branch-and-bound algorithm and a numerical simulation are presented.

scheduling; single machine; rejection; branch-and-bound

1006-3080(2017)06-0890-05

10.14135/j.cnki.1006-3080.2017.06.021

2016-06-23

慕 迪(1992-),女,安徽人,碩士生,研究方向?yàn)榻M合最優(yōu)化。

劉培海,E-mail:pliu@ecust.edu.cn

O0221.7

A