王超杰，陳光亭，陳 永，張 安

(1.杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018；2.臺州學(xué)院電子與信息工程學(xué)院，浙江 臺州 318000)

0 引 言

1 問題描述

帶服務(wù)器的具有固定序列的平行專用機排序問題的定義如下：給定1臺服務(wù)器，m臺平行專用機{M1,M2,…,Mm}和m個不相交的工件集Jk={Jk,1,Jk,2,…,Jk,nk}。其中機器Mk(1≤k≤m)需按照J(rèn)k,1,Jk,2,…,Jk,nk的順序加工工件集Jk。每個工件Jk,j(1≤j≤nk,1≤k≤m)由加載時間Sk,j和加工時間Pk,j組成，其中nk表示第k臺機器的工件數(shù)，每個工件的加載時間均為1，即Sk,j=1，Pk,j為整數(shù)。服務(wù)器只對工件進行加載操作，且一次只能對1個工件進行加載。每個工件必須先在服務(wù)器加載完畢才能開始加工。對于任意一個可行排序，Ck,nk表示機器Mk上最后1個工件的完成時間，Cmax表示工件的最大完工時間，則Cmax=max{C1,n1,C2,n2,…,Cm,nm}。目標(biāo)是尋找一個可行排序，使得工件最大完工時間盡可能小，即minCmax。

根據(jù)文獻[7]的三參數(shù)表示法,帶服務(wù)器的具有固定序列的平行專用機排序問題可表示為PD,S1|fixed-seq,sj=1|Cmax，其中PD表示平行專用機，S1表示一臺服務(wù)器，fixed-seq表示每臺平行專用機加工工件的順序是固定的，sj=1表示每個工件的加載時間均為1。PD,S1|fixed-seq,sj=1|Cmax是強NP-難的。

2 算法設(shè)計與分析

對于問題PD,S1|fixed-seq,sj=1|Cmax，文獻[7]提出了MLT算法和MRW算法，其中MRW算法是本文設(shè)計改進算法的基礎(chǔ)，其基本步驟如下。

(1)對于每臺機器Mk，計算當(dāng)前時刻工件集Jk中未被服務(wù)器加載的所有工件的處理時間(包括剩余工件的加載時間和加工時間)，即剩余時間。

(2)服務(wù)器完成當(dāng)前工件上的加載操作后，選擇當(dāng)前時刻最大剩余時間工件集Jk中可被選擇的工件進行加載操作；按此規(guī)則，直至服務(wù)器完成所有工件的加載。

(3)每個工件加載完成后，立刻在機器上加工。

對于PD,S1|fixed-seq,sj=1|Cmax問題的算法設(shè)計，一方面要考慮每臺機器上工件加工時間總和，另一方面還要兼顧服務(wù)器不能有非必要的空閑，從而保證服務(wù)器連續(xù)工作。為此，本文針對MRW算法進行改進，提出一種平行專用機總加工時間遞減的算法(Maximum the Sum of Processing-Time，MSPT)，基本步驟如下。

(2)服務(wù)器在選擇工件進行加載的優(yōu)先級為J1>J2>…>Jm。零時刻，工件J1,1在服務(wù)器上加載。每個工件加載完畢后，服務(wù)器從當(dāng)前剩余的工件序列中，挑選出允許加載的工件集，選擇該工件集中優(yōu)先級最高的工件加載。按此規(guī)則，直至服務(wù)器完成所有工件的加載。

(3)每個工件加載完成后，立即在機器上加工。

為了便于理解本文提出的MSPT算法，通過一個具體用例來闡述。

m=3時，每個工件的加載時間為Sk,j=1,每個工件的加工時間Pk,j如下：

M1∶P1,1=1;P1,2=1;P1,3=2
M2∶P2,1=1;P2,2=0;P2,3=1
M3∶P3,1=2;P3,2=0;P3,3=1

根據(jù)MSPT算法，將服務(wù)器加工的工件順序進行排列并求出MSPT算法所得排序的目標(biāo)值。

(1)令T1,T2,T3表示對應(yīng)工件集的加工時間Pk,j之和，

T1=P1,1+P1,2+P1,3=1+1+2=4
T2=P2,1+P2,2+P2,3=1+0+1=2
T3=P3,1+P3,2+P3,3=2+0+1=3

(2)根據(jù)平行專用機總加工時間遞減的原則，服務(wù)器在選擇工件進行加載的優(yōu)先級為J1>J3>J2。零時刻，服務(wù)器加載工件J1,1。1時刻，服務(wù)器允許加載的工件集為{J2,1,J3,1}，服務(wù)器選取J3,1加載；2時刻，服務(wù)器允許加載的工件集為{J1,2,J2,1}，服務(wù)器選取J1,2加載；重復(fù)以上步驟，直至所有工件加載完畢。

(3)每個工件加載完成后，立即在機器上加工。

MSPT算法執(zhí)行完畢所得的排序，如圖1所示。

圖1 MSPT算法所得排序

由圖1可知，MSPT算法所得排序的目標(biāo)值為：

證明不妨設(shè)T1≥T2≥T3，服務(wù)器選擇工件進行加載的優(yōu)先級為J1>J2>J3。設(shè)MSPT算法所得排序中，最后完工的工件為Jk,nk(k∈{1,2,3})。按照J(rèn)k,nk的歸屬情況，分成3種情形進行討論。

情形1k=1，即最后一個完工的工件為J1,n1。

情形2k=2，即最后一個完工的工件為J2,n2。

由MSPT算法可知，J2中的工件在加工時出現(xiàn)空閑的時間段與S1,j有關(guān)。再由引理1可知，

情形3k=3，即最后一個完工的工件為J3,n3。

J3中的工件在加工時出現(xiàn)空閑的時間段與S1,j和S2,j有關(guān)。再由引理1可知，

3 結(jié)束語