單位工件的平行機并行分批在線排序問題的算法

胡 丹， 農(nóng)慶琴， 方奇志

(中國海洋大學 數(shù)學科學學院，山東 青島 266100)

?

單位工件的平行機并行分批在線排序問題的算法

胡 丹， 農(nóng)慶琴， 方奇志

(中國海洋大學 數(shù)學科學學院，山東 青島 266100)

本文研究一類批容量有界的并行分批、平行機在線排序問題。模型中有n個相互獨立的工件J={J1,…,Jn}要在m臺批處理機上加工。批處理機每次可同時加工至多B(B

排序；并行批；最大完工時間；在線算法；競爭比

0 引言

分批排序問題是排序論的一個重要分支，興起于90年代初應用背景極強的一類最優(yōu)化問題。它的研究結(jié)果主要應用于大規(guī)模的現(xiàn)代化生產(chǎn)流水作業(yè)線如半導體生產(chǎn)、航空工業(yè)、鋼鐵鑄造、制鞋業(yè)等等，研究并行分批排序問題具有十分重要的實際意義。

并行分批排序可以描述為：有n個相互獨立的工件J={J1,…,Jn}待加工，工件Jj(1≤j≤n)的到達時間記為rj，加工時間記為pj。有m臺批處理機{M1,M2,…,Mm}，批處理機每次可同時加工至多B(B稱為機器的批容量)個工件，加工時間不同的工件可作為一批來加工，批的加工時間是此批中工件的加工時間的最大者。同一批中工件同時開工、同時完工。注意到當B=1時，此問題即為經(jīng)典排序問題。分批排序打破了經(jīng)典排序一臺機器在同一時間只能處理一個工件的約束，是經(jīng)典排序問題的一種推廣。根據(jù)批容量的特征，并行分批排序可分為兩種類型：批容量無界，即B=∞；批容量有界，即B

本文考慮一個批容量有界的在線并行分批排序問題：設有n個相互獨立的工件J={J1,…,Jn}要在m臺批處理機M={M1,…,Mm}上加工。工件Jj(1≤j≤n)的到達時間為rj，加工時間為1，即pj=1，批處理機每次可同時加工至多B(B

對于排序問題1|on-line,rj,B=∞|Cmax，Deng X.T.等[2]，Zhang G.C.等[3]分別設計出了競爭比是1+α的算法，并證明該排序問題不存在競爭比小于1+α的在線算法，其中α滿足等式α2+α=1。Poon C.K.和Yu W.C.[4,5]給出了一族競爭比為1+α的算法。上述算法都利用了等待的思想。不等待的算法競爭比不可能小于2，在FBLPT基礎上會達到這個界[6]。對于此問題的一些特殊情況，Richardand P.R.和Ridouard F.[7]，Yuan J.J.和Nong Q.Q.[8]給出了等待時間更少的算法。

1 算法背景

對于P|on-line,rj,pj=1,B

算法Ab(α)

若|U(t)|=0，等待，更新U(t)；

若0<|U(t)|

若|U(t)|≥B且有機器空閑，則將U(t)中B個工件組成一批在最早可空閑的機器上加工這一批。

在算法Ab(α)中，處理0<|U(t)|

2 Unified算法

若將算法Ab(α)中0<|U(t)|y，其中α≤y≤(1+α)r(t)+α,我們得到一個不同的在線算法，該算法在處理0<|U(t)|

Unified算法

若|U(t)|=0，等待，更新U(t)；

若0<|U(t)|

a)若t<α，等待，更新U(t)，r(t)；

b)若t∈[α,(1+α)r(t)+α)，可以等待，也可將U(t)中的工件組成一批在最早可空閑的機器上加工，更新t，U(t)，r(t)；

c)若t≥(1+α)r(t)+α，將U(t)中所有工件組成一批在最早可空閑的機器上加工，更新t，U(t)，r(t) 。

若|U(t)|≥B，且有機器空閑，則將U(t)中B個工件組成一批在最早可空閑的機器上加工這一批。

對于排序問題P|on-line,rj,pj=1,B

引理1[12]對于排序問題P|on-line,rj,pj=1,B

下面我們來證明Unified算法的競爭比為1+α，從而證明它的最好可能性。

定理1 Unified算法是排序問題P|on-line,rj,pj=1,B

易見，若所有機器在其停工前均無空閑時間，且除了最后一批Bk，所有批都是滿批，則我們得到一個最優(yōu)排序。因此我們只需考慮存在機器在其停工前有空閑時間或除了最后一批Bk，存在不滿批的情形。

記Tj為機器Mj在σ中的停工時間，設[t1,t2]是滿足如下特征之一的最后時間段(這里，“最后”是就右端點而言)：(1)存在機器(記為Mp)在[t1,t2]空閑，且t2

情形一 在[t1,t2]時間段內(nèi)，機器Mp空閑，且t2

設Bk在機器Mq上加工。由Unified算法及[t1,t2]的定義可知：(i)?j≠q,機器Mj在[t2,Tj]內(nèi)加工的均為滿批，且無空閑時間，機器Mq在[t2,s(Bk))內(nèi)加工的均為滿批，且無空閑時間；(ii)在[t2,Cmax)內(nèi)開工的工件均在時刻t2或之后到達。

如果t2>α，假設在機器Mp上，批Bi在t2時刻開工，即s(Bi)=t2。

情形二 在[t1,t2]內(nèi)存在機器加工某一非Bk的不滿批。

不妨記該臺機器為Mp，該不滿批為Bu，則s(Bu)=t1=t2-1。由于Bu為不滿批，由Unified算法可知s(Bu)≥α。同樣，由Unified算法及[t1,t2]的定義可知：(i)?j≠q,機器Mj在(s(Bu),Tj]內(nèi)加工的均為滿批，且無空閑時間，機器Mq在(s(Bu),s(Bk))內(nèi)加工的均為滿批，且無空閑時間；(ii)在(s(Bu,Cmax))內(nèi)開工的工件均在s(Bu)時刻之后到達。

若Bu所在的機器上有l(wèi)≥1批在Bu后加工，則這臺機器的完工時間為s(Bu)+l+1 ，由此可知s(Bu)+l+1≤Cmax≤s(Bu)+l+2(若Cmax>s(Bu)+l+2，則最后一批Bk將被安排到Bu所在機器上加工，這臺機器的完工時間將為s(Bu)+l+2，此與這臺機器上有l(wèi)≥1批在Bu后加工的假設矛盾) 。

結(jié)論得證。

3 Greedy算法Aα

在已有算法Ab(α)中，每一批將被滯后到(1+α)r(t)+α時刻加工，其中r(t)為U(t)中最晚工件的到達時間。我們設計一個簡單的Greedy算法Aα，加工工件時不需要每批均判斷是否t≥(1+α)r(t)+α，而是在α時刻后工件到達后只要有機器空閑就馬上加工。

Greedy算法Aα描述如下：

Greedy算法Aα

若|U(t)|=0，等待，更新U(t)；

若0<|U(t)|

a)若t<α，等待，更新U(t)，r(t)；

b)若t≥α且有機器空閑，將U(t)中所有工件組成一批在最早可空閑的機器上加工，更新U(t),r(t)。

若|U(t)|≥B且有機器空閑，則將U(t)中B個工件組成一批在最早可空閑的機器上加工這一批。

Greedy算法Aα在處理0<|U(t)|

Greedy算法Aα還可簡述為：

當t<α，只要|U(t)|≥B且有機器空閑，則將U(t)中B個工件組成一批在最早可空閑的機器上加工這一批；

當t≥α，只要|U(t)|≠0且有機器空閑，則將|U(t)|中個min{|U(t)|,B}個工件組成一批在最早可空閑的機器上加工這一批。

推論1 Greedy算法Aα是排序問題P|on-line,rj,pj=1,B

對上述三個在線算法進行比較, 可以看出，處理0

[1] Graham R L, Lawler E L, Lenstra J K, Rinnooy Kan A H G. Optimization and approximation in deterministic sequencing and scheduling[J]. A survey. Annals of Discrete Mathematics, 1979, 5(2): 287-326.

[2] Deng X T, Poon C K, Zang Y Z. Approximation algorithms in batch processing[J]. Journal of Combinatorial Optimization, 2003, 7: 247-257.

[3] Zhang G C, Cai X Q, Wong C K. On-line algorithms for minimizing makespan on batch processing machines[J]. Naval Research Logistics, 2001, 48: 241-258.

[4] Poon C K, Yu W C. A flexible on-line scheduling algorithm for batch machine with infinite capacity[C],5th Conference on Optimization: Techniques and Application(ICOTA’01), Hong Kong, December 2001.

[5] Poon C K, Yu W C. A flexible on-line scheduling algorithm for batch machine with infinite capacity[J]. Annals of Operations Research, 2005, 133: 175-181.

[6] Liu Z H, Yu W C. Scheduling one batch processor subject to job release dates[J]. Discrete Applied Maths, 2000, 105: 129-136.

[7] Richardand P Q, Ridouard F. On-line scheduling on a single batching machine to minimize the makespan[C]. 6th International Conference on Industrial Engineering and Production Management(IEPM’03). Parto(Portugal). May, 2003.

[8] 原晉江, 農(nóng)慶琴.平行批排序最小化最大完工時間在線算法的一個注記[J].鄭州大學學報(理學版),2006,38(3):1-3.

[9] Poon C K, Yu W C. On-line scheduling algorithm for a batch machine with finite capacity[J]. Journal of Combinatorial Optimization, 2005, 9(2): 167-186.

[10] Liu P H, Lu X W, Fang Y. A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines[J]. Journal of Scheduling , 2012, 15: 77- 81.

[11] Tian J, Cheng T C E, Ng C T, Yuan J J. Online scheduling on unbounded parallel-batch machines to minimize the makespan[J]. Information Processing Letters, 2009, 109: 1211-1215.

[12] Zhang G C, Cai X Q, Wong C K. Optimal on-line algorithms for scheduling on parallel batch processing machines[J]. IIe Transactions, 2003, 35: 175-181.

Algorithms for an Online Parallel-batching Scheduling Problem with Unit Jobs

HU Dan, NONG Qing-Qin, FANG Qi-Zhi

(SchoolofMathematicalScience,OceanUniversityofChina,Qingdao266100,China)

In this paper, we consider the problem of on-line scheduling a set of independent jobsJ={J1,…,Jn}on parallel-batching processing machines{M1,…,Mm}. Each machine can handle up toBjobs as a batch simultaneously, and all the jobs in a batch start and complete at the same time. Once a batch is started, it cannot be stopped until its completion. We deal with the bounded case where the capacity of the machines is finite, i.e.,B

scheduling; parallel-batching; makespan; on-line algorithm; competitive ratio

2012- 08-29

國家自然科學基金資助項目(11201439)；國家自然科學基金資助項目(11271341)；教育部博士點專項基金新教師基金(20120132120001)；山東省自然科學基金(ZR2012AQ12)

胡丹(1989-)女，碩士研究生，研究方向：組合最優(yōu)化；農(nóng)慶琴(1978-)女，副教授，博士，研究方向：組合最優(yōu)化，排序；方奇志(1966-)女，教授，博士，研究方向：組合最優(yōu)化，計算復雜性。

O225

A

1007-3221(2015)01- 0137- 05