同型平行機(jī)上的在線分批排序問題

盧文麗

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

同型平行機(jī)上的在線分批排序問題

盧文麗

（淄博師范高等?？茖W(xué)校 教育科學(xué)系，山東 淄博 255100）

排序；分批排序；競爭比；同型機(jī)；在線算法

1 引言

排序問題的理論與應(yīng)用研究自二十世紀(jì)六十年代興起以來，經(jīng)過四十多年的發(fā)展已經(jīng)成為組合優(yōu)化領(lǐng)域的重要組成部分，被廣泛應(yīng)用到網(wǎng)絡(luò)通信、自動(dòng)化生產(chǎn)調(diào)度和物流管理等多個(gè)方面，從而使排序問題極具生命力和研究價(jià)值.

分批排序問題最早是在半導(dǎo)體集成電路制造的最后測(cè)試階段預(yù)燒作業(yè)過程中提煉出來的一類重要排序問題，它是一種新型的排序問題，是經(jīng)典排序問題的推廣，在現(xiàn)代化生產(chǎn)的各個(gè)領(lǐng)域都得到了廣泛的應(yīng)用，隨著大規(guī)模的現(xiàn)代化生產(chǎn)的發(fā)展，研究分批排序問題具有重要的實(shí)際意義.

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

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

2 問題描述

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

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

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

3 算法描述

對(duì)于1|B|Cmax的離線情形,C.Y.Lee和R.Uzsoy[5]給出了一個(gè)多項(xiàng)式的FBLPT算法,且此算法是最優(yōu)的.

FBLPT算法：

步驟1把工件按加工時(shí)間非增的次序編號(hào)使p1≥p2≥…≥pn；

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

BLPT算法：

步驟2按pk非增的次序排列各批次序，當(dāng)機(jī)器要出現(xiàn)空閑，就把排在前面的還未加工的批安排到這臺(tái)機(jī)器上加工.

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

MBLPT算法：

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

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

綜上所述，定理成立.

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

4 結(jié)論

〔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