同型平行機上的在線分批排序問題

盧文麗

（淄博師范高等專科學校 教育科學系，山東 淄博 255100）

同型平行機上的在線分批排序問題

盧文麗

（淄博師范高等專科學校 教育科學系，山東 淄博 255100）

排序；分批排序；競爭比；同型機；在線算法

1 引言

排序問題的理論與應用研究自二十世紀六十年代興起以來，經過四十多年的發展已經成為組合優化領域的重要組成部分，被廣泛應用到網絡通信、自動化生產調度和物流管理等多個方面，從而使排序問題極具生命力和研究價值.

分批排序問題最早是在半導體集成電路制造的最后測試階段預燒作業過程中提煉出來的一類重要排序問題，它是一種新型的排序問題，是經典排序問題的推廣，在現代化生產的各個領域都得到了廣泛的應用，隨著大規模的現代化生產的發展，研究分批排序問題具有重要的實際意義.

分批排序問題可描述為：有固定的n個工件J1，J2，…，Jn需要在一臺或多臺批處理機上加工，每個工件Jj有工時pj、到達時間rj等，其到達時間和工時不一，要將工件分批加工.處理機一次最多能加工B個工件,工件加工過程中不允許被打斷,也不允許移走或加入新工件.每一批的加工時間為屬于該批的工件中最長工件的工時,開工時間應大于或等于該批中最晚到達的工件的到達時刻,且屬于同一批的工件同時開工并同時完工.工件Jj的完工時間為所在批的完工時間，問題是如何合理地安排機器和工件，怎樣分批，如何排序，使得某些要求（目標函數）達到最優，這就是所謂的分批排序問題.

由于分批排序問題具有較強的應用背景又是經典排序的推廣，所以此類問題的研究工作于20世紀90年代以來很快得到發展并活躍起來.對于1|rj，B|Cmax的離線情形，1992年，C.Y.Lee等[1]在rj=0時給出了一些較基本的結果.Zhang和Deng[2]對具有不同到達時間情況的極小化加權總完工時間問題，給出了其N P完備性的證明，并給出了常數個到達時間和加工時間時的精確算法.

2 問題描述

在本文中我們研究同型平行機上的在線分批排序問題.其模型為：有m臺速度相同的機器，現有n個工件不同時到達，假設工件的到達時間為rj，1≤j≤n，每個工件在到達前的信息都是未知的，只有到達后才能知道其所有信息，問怎樣對工件進行分批，如何安排加工，使各批的最大完工時間盡可能的小.

本文我們將首次考慮更一般的問題pm|rj∈{0,r}，B|Cmax的在線問題，即所有工件有不同的加工時間，但只有兩個到達時間的平行機在線分批排序問題.在給出算法之前先簡單介紹相關符號的定義：

用J1，J2分別表示0時刻，r時刻到達工件的工件集，則J1∪J2即是所有工件的工件集.若用BLPT加工J1，則在最后一批工件完工時，各機器上的完工時間設為Ti1(i=1,2,…,m)，其=m a x{Ti1|i=1,2,…m}=Tk1；類似，若用BLPT加工J2，則所有工件完工時，各機器的完工時間為Ti2(i=1,2,…,m)，m a x{Ti2|i=1,2,…m}；若J1中部分工件與J2中工件，運用BLPT算法加工，則得到的最大完工時間記為.上述相應的最優排序分別記為C1*，C2*，；用C*表示本問題最優解；另外設pkt為用BLPT加工J1中，第k臺機器上最后完工的工件.

3 算法描述

對于1|B|Cmax的離線情形,C.Y.Lee和R.Uzsoy[5]給出了一個多項式的FBLPT算法,且此算法是最優的.

FBLPT算法：

步驟1把工件按加工時間非增的次序編號使p1≥p2≥…≥pn；

步驟3任意安排各批的次序.

BLPT算法：

步驟2按pk非增的次序排列各批次序，當機器要出現空閑，就把排在前面的還未加工的批安排到這臺機器上加工.

利用上述分批思想，我們對于pm|rj∈{0,r},B|Cmax的在線問題，給出了一個MBLPT算法.

MBLPT算法：

步驟1把J1中工件按BLPT算法進行分批，安排在各機器上加工；

步驟2若J2中工件在J1中所有工件都完工后到達，即，則用BLPT算法在r時刻開始加工J2；

綜上所述，定理成立.

根據以上分析，我們有下面的推論.

4 結論

〔1〕Lee C, Uzsoy R, Martin Vega. EfficienL algorithms for scheduling semiconductor buming operations [J]. Operations Research, 1992, 40: 764-755.

〔2〕Xiaotie Deng, Yuzhong Zhang. Miniming mean resposetime in batch progressing system [J]. Lecture Notes inComputer Science, 1999, 1627: 231-240.

〔3〕Zhang. G, Cai. X, C. K. Wong. On-line algorithms forminimizing makespan on batch processing machines [J].Naval Research Logistics, 2001, 48: 241-259.

〔4〕Zhang. G, Cai. X, C. K. Wong. Optimal on-line algorithmsfor scheduling on parallel batch processing machines[J]. IIE Transaction, 2003, 35: 175-181.

〔5〕C. Y. Lee, R. Uzsoy. Minimizing makespan on a singlebatch processing machines with dynamic job arrivals [J].IJPR, 1999, 37: 219-236.

O223

A

1673-260X（2010）03-0017-02