帶拒絕和到達時間的單機排序問題

慕 迪, 劉培海

(華東理工大學數學系,上海 200237)

帶拒絕和到達時間的單機排序問題

慕 迪, 劉培海

(華東理工大學數學系,上海 200237)

研究了一個單機帶拒絕的排序問題,目標函數是最小化接受工件的最大完工時間與所有被拒絕工件的拒絕費用之和。首先給出了此問題的混合整數規劃模型,并得到了最優解的一些性質。最后給出了一個分支定界算法,并給出了數值模擬的結果。

排序; 單機; 拒絕; 分支定界

1 最優解的性質

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

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

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

證明 (1)假設在最優排序π*中ji被拒絕,并且ji滿足ri≤rj,pi/wi≤1,因為π*接受了工件jj,若在Cmax(π*)時刻開始加工ji,則目標函數值不會增加,這與π*的最優性矛盾,因此ji在π*中也一定被接受;

(2) 同理可證。

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

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

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

(2) 同理可證。

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

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

性質4在最優時間表π*中,設最后加工工件開始加工的時間為tmax,則?t

(1) 機器在t時刻忙碌,即在加工某個工件;

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

2 目標問題的上下界

2.1 整數規劃模型

假設所有工件已經按照到達時間的先后順序重新編號,即

r1≤r2≤…≤rn:

(1)

(2)

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

(3)

其中,

Cmax為最大完工時間;W為所有被拒絕工件的拒絕費用和;M為一個足夠大的數。

目標函數為:

minZ=Cmax+W

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

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

minZk=Cmax,k+Wk

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

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

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),假設在某個最優解中

由式(4)可得

(7)

(8)

所以必然有

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

(9)

其中1≤j≤i。

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

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

重復上述過程,總可以找到一個滿足性質3的最優解。

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

表1 例1中各工件參數

設上述算法所得下界UB對應的排序為π1,顯然這也是問題(P)的一個松弛解。

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

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

步驟1 在排序π1中,

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

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

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

例2:同樣是例1中的4工件問題,現在求解上界。由例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},計算得到上界UB=Cmax+w4=8+2=10。

3 分支定界算法

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

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

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

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

步驟3 刪除規則:若在某個節點有LBk>UB,則將這個節點刪去;

步驟4 停止條件:若已經考慮了所有分支,則停止計算,此時得到局部最優解。

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

表2 例3中的各工件參數

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

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

4 數值模擬

首先利用Cplex軟件對整數規劃模型進行求解,并且用C++語言來編譯分支定界算法,為以下參數的每種組合產生200個實例:

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

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

表3～表6分別示出了當dc∈{0.2,0.5},rc∈{0.5,1,1.5}時,整數規劃(IP)的運行結果。可以看出,整數規劃模型基本上能得出問題(P)的最優解,并且在1 000個工件內效率都比較高,但是運行時間平均比分支定界算法要長。

表3 n=50時整數規劃運行結果

表4 n=200時整數規劃運行結果

表5 n=500時整數規劃運行結果

表6 n=1 000時整數規劃運行結果

表7 分支定界算法運行結果

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

符號說明：

n——工件個數

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

rj——工件jj的到達時間

pj——工件jj的加工時間

wj——工件jj的拒絕費用

Cj——工件jj的完工時間

R——拒絕工件集合

A——接受工件集合

Z(π)=Cmax(A)+W——時間表π的目標函數值

[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-),女,安徽人,碩士生,研究方向為組合最優化。

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

O0221.7

A