李海霞， 朱路寧， 趙晟珂

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

機器帶準備時間的同類機分批排序算法

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

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

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

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

1 問題背景及描述

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

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

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

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

苗，張［17］利用復制法已給出了Pm｜B｜∑ωjC j的NP－完備性證明.因而易知題至少也應是NP－難的.但該問題在工件有相同的標準加工時間的情況下，卻是多項式時間可解的.

FBLW算法（fully batch largest weight）.

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

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

步驟3：將分好的每批工件看作一個工件，按批的下標不減序依次安排在批處理機上進行加工，且不讓批處理機空閑.

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

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

改進后的算法為：

算法A1.

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

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

步驟3：把批處理機的準備時間看作其在零時刻開始加工的第一個工件.

步驟4：將分好的每批工件看作一個工件，按批的下標不減序依次安排在其最早完工的批處理機上進行加工，不讓批處理機空閑.

顯然該算法的計算復雜性為O （nlogn）.

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

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

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

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

若不然，假設ωi＞ωj＞ωk，且不妨設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)整后的排序中的完工時間分別記為Cx與C′x.

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

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

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

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

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

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

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

由算法A1可知W i≥W j，i＞j，而且Bi的完工時間早于B j.所以運用算法A1所得到的排序為最優(yōu)序.

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

在前一部分中，就工件標準加工時間相同且機器帶有準備時間的同類機分批排序問題進行了討論.接下來，將在此基礎上進一步考慮工件具有常數(shù)個到達時間的問題，即

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

4 結 論

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

［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］.曲阜師范大學學報，2004，30（2）：33－35.

［15］苗翠霞，張玉忠.極小加權總完工時間的分批排序問題［J］.運籌學學報，2005，9（2）：82－86.

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

［17］張玉忠，苗翠霞.復制法及其在分批排序中的應用［J］.曲阜師范大學學報，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