機(jī)器帶準(zhǔn)備時(shí)間的同類機(jī)分批排序算法

李海霞， 朱路寧， 趙晟珂

（1.山東水利職業(yè)學(xué)院基礎(chǔ)科學(xué)部，山東日照 276826； 2.曲阜師范大學(xué)運(yùn)籌與管理學(xué)院，山東日照 276826）

機(jī)器帶準(zhǔn)備時(shí)間的同類機(jī)分批排序算法

李海霞1， 朱路寧2， 趙晟珂2

（1.山東水利職業(yè)學(xué)院基礎(chǔ)科學(xué)部，山東日照 276826； 2.曲阜師范大學(xué)運(yùn)籌與管理學(xué)院，山東日照 276826）

討論了兩類機(jī)器帶準(zhǔn)備時(shí)間的同類機(jī)分批排序問題.對工件無到達(dá)時(shí)間及有常數(shù)個(gè)到達(dá)時(shí)間，目標(biāo)函數(shù)為極小化加權(quán)總完工時(shí)間這兩類問題進(jìn)行研究，給出了兩個(gè)最優(yōu)算法，并對算法及其計(jì)算復(fù)雜性給予了分析與證明.

分批排序；準(zhǔn)備時(shí)間；FBLW算法；最優(yōu)性

1 問題背景及描述

排序問題是組合最優(yōu)化領(lǐng)域中的一類重要問題，它在生產(chǎn)管理與調(diào)度、晶體加工［1，2］、網(wǎng)絡(luò)通信、航空工業(yè)［3，4］、鋼鐵鑄造［5］、計(jì)算機(jī)數(shù)據(jù)處理以及物流管理等方面有著廣泛的實(shí)際應(yīng)用背景.產(chǎn)生于20世紀(jì)90年代的分批排序問題是從半導(dǎo)體生產(chǎn)過程的最后階段提煉出來的一類重要排序問題［6］.國內(nèi)外許多專家學(xué)者對其進(jìn)行了研究并取得了許多重要的成果［7－10］.對目標(biāo)函數(shù)為極小化加權(quán)總完工時(shí)間的平行機(jī)排序問題，Bruno和Coffman［11］證明P2‖是NP－難的，因而分批排序問題Pm｜B｜｜B｜也應(yīng)是NP－難的，Cheng等［12］對Pm｜B｜給出了時(shí)間復(fù)雜性為o（mn m＋1）的動態(tài)規(guī)劃算法.對于工件有不同到達(dá)時(shí)間的情況，Deng和Zhang［13］證明了1｜rj，B≥n｜∑ωjC j是NP－完備問題，并給出了當(dāng)工件到達(dá)時(shí)間與工件加工時(shí)間個(gè)數(shù)為常數(shù)的動態(tài)規(guī)劃算法.丁際環(huán)等［14］就工件具有兩個(gè)到達(dá)時(shí)間的、目標(biāo)函數(shù)為極小化加權(quán)總完工時(shí)間的排序問題證明了其NP－完備性，并給出了一個(gè)2－近似算法.在所有工件有相同的加工時(shí)間的特殊情況下，苗翠霞、張玉忠［15］給出了最優(yōu)算法.

隨著社會生產(chǎn)的不斷發(fā)展，大量的新型排序問題不斷涌現(xiàn)，機(jī)器帶準(zhǔn)備時(shí)間的情況便是其中之一.此前傳統(tǒng)的經(jīng)典排序問題總是假設(shè)機(jī)器在零時(shí)刻就可以加工工件，但實(shí)際情況往往并非如此，比如機(jī)器在開工之前要做日常的維護(hù)工作，在此期間不能加工工件，這段時(shí)間就稱為機(jī)器的準(zhǔn)備時(shí)間，并用Ri表示機(jī)器Mi的準(zhǔn)備時(shí)間.由現(xiàn)有文獻(xiàn)不難得到Qm，Ri｜B｜，排序問題也是NP－難的.

本文在［16］的研究基礎(chǔ)上首次討論了在所有工件的標(biāo)準(zhǔn)加工時(shí)間均相同的條件下的兩類機(jī)器帶準(zhǔn)備時(shí)間的同類機(jī)排序問題.分別對工件無到達(dá)時(shí)間及有常數(shù)個(gè)到達(dá)時(shí)間，且目標(biāo)函數(shù)均為極小化加權(quán)總完工時(shí)間這兩類排序問題進(jìn)行了研究.用三參數(shù)表示法可表示為

2 對于Qm，Ri∑ωjC j問題的精確算法

苗，張［17］利用復(fù)制法已給出了Pm｜B｜∑ωjC j的NP－完備性證明.因而易知題至少也應(yīng)是NP－難的.但該問題在工件有相同的標(biāo)準(zhǔn)加工時(shí)間的情況下，卻是多項(xiàng)式時(shí)間可解的.

FBLW算法（fully batch largest weight）.

步驟1：將工件按權(quán)重不增的順序重新編號，即ω1≥ω2≥…≥ωn.

步驟2：對工件進(jìn)行分批.將前B個(gè)工件作為第一批，記為B1；次B個(gè)作為第二批，記為B2，…，依次進(jìn)行下去.

步驟3：將分好的每批工件看作一個(gè)工件，按批的下標(biāo)不減序依次安排在批處理機(jī)上進(jìn)行加工，且不讓批處理機(jī)空閑.

由FBLW算法可知，n個(gè)工件可以分為批或＋1批，除最后一批不滿外其余各批均是滿的，顯然該算法的時(shí)間復(fù)雜性為O （nlogn）.

在該算法的基礎(chǔ)上，需對其進(jìn)行改進(jìn)使之能夠有效的解決所要研究的問題為此，結(jié)合ECTF（earliest completion time first）算法，對其作如下調(diào)整：首先，將批處理機(jī)的準(zhǔn)備時(shí)間看作在零時(shí)刻加工的第一個(gè)工件.其次，在對每批工件進(jìn)行安排時(shí)對批處理機(jī)進(jìn)行選擇.

改進(jìn)后的算法為：

算法A1.

步驟1：將工件按權(quán)重不增的順序重新編號，即ω1≥ω2≥…≥ωn.

步驟2：對工件進(jìn)行分批.將前B個(gè)工件作為第一批，記為B1；次B個(gè)作為第二批，記為B2，…，依次進(jìn)行下去.

步驟3：把批處理機(jī)的準(zhǔn)備時(shí)間看作其在零時(shí)刻開始加工的第一個(gè)工件.

步驟4：將分好的每批工件看作一個(gè)工件，按批的下標(biāo)不減序依次安排在其最早完工的批處理機(jī)上進(jìn)行加工，不讓批處理機(jī)空閑.

顯然該算法的計(jì)算復(fù)雜性為O （nlogn）.

定理1算法A1能最優(yōu)的解決問題

為證明方便，算法A1中工件按權(quán)重不增的順序重新編號后即為ω1≥ω2≥…≥ωn，下述證明中“每批中工件的編號是連續(xù)的”即指按算法A1所得的每批工件是按權(quán)重的編號連續(xù)的.

證為證明此定理，我們需要從三個(gè)方面給以證明.首先需證明每批中工件的編號是連續(xù)的.其次還要證明除工件Jn所在的批可能不滿外其余的批均為滿批.最后需證明該批的序號與該批的完工時(shí)間序相一致因而是最優(yōu)序.其中第二部分的證明過程與［13］的證明類似，在此不再贅述.下面僅就余下兩部分給出證明.

首先證明每批中的工件編號是連續(xù)的.

若不然，假設(shè)ωi＞ωj＞ωk，且不妨設(shè)Ji∈Bi，Jj∈Bj，Jk∈Bi，下面分情況討論.

1.Bi批在B j批之前加工.交換J j與J k的加工順序，即將J i與J j放在B i中加工，而J k放在B j中加工，其他工件保持原序.令工件Jx（x＝i，j，k）在原先排序和調(diào)整后的排序中的完工時(shí)間分別記為Cx與C′x.

情形1：若Bi與B j在同一臺批處理機(jī)上加工，因而批處理機(jī)的準(zhǔn)備時(shí)間相同記為R，不妨設(shè)Bi的完工時(shí)間為R＋xp，Bj的完工時(shí)間為R＋（x＋y）p，x，y為兩個(gè)大于零的整數(shù)，則有

情形2：若Bi與B j不在同一臺批處理機(jī)上加工，不妨設(shè)Bi批在第Mt（t＝i，j）臺批處理機(jī)上加工，且Mt的準(zhǔn)備時(shí)間為R t（t＝i，j），可設(shè)Bi的完工時(shí)間為R i＋xp，Bj的完工時(shí)間為R j＋yp，其中x，y為兩個(gè)大于零的整數(shù).因?yàn)锽i在B j之前加工，由算法易知Bj的完工時(shí)間不會比B i的完工時(shí)間早，即Ri＋xp≤Rj＋yp，則

2.Bj批在B i批之前加工.交換Ji與J j的加工順序，即將Jj與J k放在B i中加工，而Ji放在B j中加工，其他工件保持原序.我們用上述（1）的證明方法同樣分兩種情形進(jìn)行討論.

情形1：若Bi與B j在同一臺批處理機(jī)上加工，不妨設(shè)Bi的完工時(shí)間為R＋（x＋y）p，Bj的完工時(shí)間為R＋xp，x，y為兩個(gè)大于零的整數(shù)，則易得

情形2：若Bi與B j不在同一臺批處理機(jī)上加工，設(shè)Bi的完工時(shí)間為R i＋xp，Bj的完工時(shí)間為R j＋yp，其中x，y為兩個(gè)大于零的整數(shù).因?yàn)锽j批在B i批之前加工，由算法易知Bi的完工時(shí)間不會比B j的完工時(shí)間早，即Ri＋xp≥Rj＋yp，則由條件可得

3.若Bi與B j同時(shí)完工，則可以將Ji與J k交換，或者Jj與J k交換，其他工件不變.由于標(biāo)準(zhǔn)加工時(shí)間相等，則總的目標(biāo)函數(shù)值是不變的.

通過上述證明可以看出，經(jīng)過算法調(diào)整后的目標(biāo)函數(shù)值顯然不劣于調(diào)整前的排序，將原先排序中所有滿足調(diào)整條件的工件均對其進(jìn)行如上調(diào)整，則總的目標(biāo)函數(shù)值不變或者更優(yōu)，因而每批中的工件的編號是連續(xù)的.

由算法A1可知W i≥W j，i＞j，而且Bi的完工時(shí)間早于B j.所以運(yùn)用算法A1所得到的排序?yàn)樽顑?yōu)序.

3 關(guān)于Qm，Ri｜B，p j＝p，rj∈｛r1，…，rk｝｜∑ωjC j的最優(yōu)算法

在前一部分中，就工件標(biāo)準(zhǔn)加工時(shí)間相同且機(jī)器帶有準(zhǔn)備時(shí)間的同類機(jī)分批排序問題進(jìn)行了討論.接下來，將在此基礎(chǔ)上進(jìn)一步考慮工件具有常數(shù)個(gè)到達(dá)時(shí)間的問題，即

其中k為常數(shù).同樣給出解決這一問題的一個(gè)最優(yōu)算法.

4 結(jié) 論

本文首次就排序機(jī)器帶準(zhǔn)備時(shí)間的同類機(jī)上的分批排序問題進(jìn)行了研究，給出了兩個(gè)最優(yōu)算法A 1和A2，并分別分析了算法的計(jì)算復(fù)雜性.本文所得結(jié)果是在一個(gè)相當(dāng)強(qiáng)的條件下得到的，對于更為一般的情況，該類問題為NP－難的，因此找到更好的近似算法，并分析他們的最差性能比是我們下一步目標(biāo).

［1］Uzsoy R，Lee C Y and Martin－Vega L A.A review of production planting and scheduling models in semiconductor industry，Part I：system characteristics，performance evaluation and production planning［J］.IIE Transaction，1992，24（4）：47－60.

［2］Uzsoy R，Lee C Y and Martin－Vega L A.A review of production planting and scheduling models in semiconductor industry Part II：shop floor control［J］.IIE Transaction on Scheduling and Logistics，1994，26（5）：44－55.

［3］Zee D J，Vander A，Van Harten and Schuur P C.Dynamic job assignment heuristics for multi－server batch operations－A cost based approach［J］.International Journal of Production Research，1997，35（11）：3063－3093.

［4］Zee D J，Vander A，Van Harten and Schuur P C.Online scheduling of multi－sever batch operations［J］.IIE Transactions，2001，33（7）：569－586.

［5］Mathirajan Mand Sivakumar A I.Scheduling of batch processors in semiconductor manufacturing－a review［R］.Symposium，National University of Sinngapore，Singapore MIT Alliance，January 2003.

［6］Fanti MP，Maione B P，Iscitelli G and Turchiano B.Heuristic scheduling of jobson a multi－product batch processing machine［J］.International Journal of Production Research，34（8）：2163－2186.

［7］Brucker P，Ladky G，Hoogeveveen A，Kovalyov H，Potts MY，Tautenhahn C N T and Van de Velde S L.Scheduling a batching machine［J］.Journal of Scheduling，1998，1（1）：31－54.

［8］Baptiste P.Batching identical jobs［J］.A mathematical Methods of Operations Research，2000，22（4）：501－524.

［9］Albers S and Brucker P.The complexity of one－machine batching problem［J］.Discrete Applied mathematics，1993，47（1）：87－107.

［10］Potts C N and Lovalyov MY.Scheduling with batching：a review［J］.European Journal of Operational Research 2000，120（2）：228－249.

［11］Bruno J，Coffman E G Jr，Sethi R.Scheduling independent tasks to reduce mean finishing time［J］.Communications of the ACM，1974，17（7）：382－387.

［12］Cheng T C E，Chen Z L，Kovalyov MY and Lin B MT.Parallel－machine batching and scheduling to minimize total completion time［J］.IIE Transactions 1996，28（11）：953－956.

［13］Deng X，Poon C K and Zhang Y.Approximation algorithms in batch processing［J］.Journal of Combinational Optimization，2003，7（3）：247－257.

［14］丁際環(huán)，等.1｜rj∈0，r，B｜∑Cj［J］.曲阜師范大學(xué)學(xué)報(bào)，2004，30（2）：33－35.

［15］苗翠霞，張玉忠.極小加權(quán)總完工時(shí)間的分批排序問題［J］.運(yùn)籌學(xué)學(xué)報(bào)，2005，9（2）：82－86.

［16］張玲玲，等.一種極小化ωj Cj的分批排序問題的算法［J］.洛陽大學(xué)學(xué)報(bào)，2005，21（4）：43－45.

［17］張玉忠，苗翠霞.復(fù)制法及其在分批排序中的應(yīng)用［J］.曲阜師范大學(xué)學(xué)報(bào)，2004.30（2）：33－35.

Batch Scheduling Algorithms for Similar Machines with Readiness Time

LIHai－xia1，ZHULu－ning2，ZH AOSheng－ke2
（1.Department of Basic Science，Shandong Water Polytechnic，Rizhao 276826，China；2.Operation Research and Management，Qufu Normal University，Rizhao，276826，China）

This paper investigates sorting problems of two classes of similar machines with readiness time.For problems that have no or constant arrival times and which object functions are minimizing weighted completion time，we present the analysis and proof of two optimal algorithms and their complexities.

batch scheduling；readiness time；FBLW；optimality

O223

A

1672－1454（2011）04－0122－06

2010－09－26