工件加工時間非增的并行分批排序問題的最優(yōu)在線算法?

農(nóng)慶琴， 苗利輝

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

工件加工時間非增的并行分批排序問題的最優(yōu)在線算法?

農(nóng)慶琴， 苗利輝

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

排序；并行批；在線；算法；競爭比

并行分批排序模型中的機(jī)器是批處理機(jī)，每次可同時加工至多B(B≥2，稱為機(jī)器的批容量)個工件。根據(jù)批容量的特征，并行分批排序可分為2種類型：批容量無界(記為B=∞)；批容量有界(記為B

Cmax=max1≤j≤nCj

最小，其中Cj為工件Jj的完工時間。采用R.L.Graham等[1]提出的三參數(shù)法，該問題可記為

1|on-line,rj,pjnon-increasing,B

衡量一個在線排序算法A的性能最常用的指標(biāo)是它的競爭比RA。對于最小化目標(biāo)函數(shù)的在線排序問題，競爭比RA定義為對問題的所有實(shí)例運(yùn)行該在線排序算法所得目標(biāo)函數(shù)值與相應(yīng)離線排序的最優(yōu)值比值的上確界，即

關(guān)于并行分批排序問題的研究是近十多年來排序論的研究熱點(diǎn)。學(xué)者們最先著手的是單機(jī)、批容量無界的排序模型的研究。對于排序問題1|on-line,rj,B=∞|Cmax，DengXT等[2]，ZhangGC等[3]分別獨(dú)立地設(shè)計(jì)出了競爭比是1+α的在線算法，并證明該排序問題不存在競爭比小于1+α的在線算法，從而證明相應(yīng)算法的最優(yōu)性，其中α滿足等式α2+α=1。PoonCK等[4-5]給出了一族競爭比均為1+α的在線算法。上述算法都利用了等待的思想，不等待的在線算法競爭比不可能小于2[6]。對于此問題的一些特殊情況，RichardandPR等[7]，YuanJJ等[8]給出了等待時間更少的在線算法。

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

給出了競爭比為1+α的在線算法，并證明該算法是最優(yōu)的。

本文研究批容量有界、工件的加工時間非增的并行分批在線排序問題

1|on-line,rj,pjnon-increasing,B

給它設(shè)計(jì)一個競爭比是1+α的在線算法，并證明該算法是最優(yōu)的。

1 本文主要結(jié)果

探討批容量有界、工件的加工時間非增的并行分批在線排序問題

1|on-line,rj,pjnon-increasing,B

的在線算法。不妨設(shè)r1≤r2≤…≤rn，由于工件的加工時間非增，有不等式p1≥p2≥…≥pn成立。記U(t)為t時刻已到達(dá)但尚未開工的工件集合，|U(t)|為U(t)中工件的數(shù)目，算法如下：

算法EF(EarlyFirst)：

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

若0<|U(t)|

若|U(t)|≥B：如果有機(jī)器空閑，則將U(t)中B個編號最小的(即最早到達(dá)的)工件組成一批開始加工，更新U(t)。

該算法的主要思想是：在機(jī)器空閑時需要決定是否加工待加工的工件，當(dāng)待加工的工件數(shù)超過批的容量B時，優(yōu)先選取早到的工件進(jìn)行加工(由于工件的加工時間非增，這里實(shí)際上意味著長工件被優(yōu)先選取)；當(dāng)待加工的工件數(shù)不足B個時，根據(jù)當(dāng)前的時刻是否大于αp1再決定是否開工——若當(dāng)前時刻小于αp1不加工，繼續(xù)等待新工件；若當(dāng)前時刻大于或等于αp1，不再等待，立刻將當(dāng)前待加工的工件作為一批開始加工。αp1是一個關(guān)鍵時刻，在此時刻之前，只有待加工的工件達(dá)到B個才考慮開始加工，在此時刻之后，一旦有工件待加工、機(jī)器空閑，就立刻開始加工。

排序問題1|on-line,rj,B

定理1.1 對于1|on-line,rj,B

顯然，每個工件加工時間均為1的實(shí)例是排序問題1|on-line,rj,pjnon-increasing,B

推論1.1 對于排序問題

1|on-line,rj,pjnon-increasing,B

不存在競爭比小于1+α的在線算法。

為了分析算法EF的競爭比，下面介紹一種分批規(guī)則。

FBLPT(FullBatchLongestProcessingTime)規(guī)則：

步驟一 將所有工件按加工時間的非增順序排列，形成一個隊(duì)列L。

步驟二 若隊(duì)列L的工件數(shù)不少于B個，將排在最前的B個置于一批中，并將這B個工件從隊(duì)列L中刪除；否則將L中余下的所有工件置于一批中。

定理1.2 算法EF是在線排序問題

1|on-line,rj,pjnon-increasing,B

的競爭比為1+α的在線算法。

證明 給定任一實(shí)例I，算法EF輸出的排序記為σ。設(shè)σ中總共有l(wèi)批，分別記為B1,B2,…,Bl，并設(shè)

s(B1)

其中s(Bi)(1≤i≤l)為批Bi的開工時間。算法EF優(yōu)先加工早到達(dá)的工件，而早到達(dá)的工件加工時間較長，因此必有Bi(1≤i≤l-1)中的工件加工時間均不小于它之后的批中工件的加工時間，于是

p(B1)≥p(B2)≥…≥p(Bl)

成立，其中p(Bi)(1≤i≤l)為批Bi的加工時間。顯然，最長工件J1必在B1中。

設(shè)排序σ中[t1,t2]是時間區(qū)間[0,Cmax]內(nèi)滿足如下特征之一的最后時間段：(1)機(jī)器在[t1,t2]空閑;(2)機(jī)器在[t1,t2]內(nèi)加工某一非Bl的不滿批。

設(shè)排序σ中t2之后開工的批分別為

Bk,Bk+1,…,Bl，

情形一 在[t1,t2]時間段內(nèi)機(jī)器空閑。

若t2>αp1，因?yàn)樗惴‥F在αp1時刻之后的排序規(guī)則是一旦有工件待加工、機(jī)器空閑，就立刻開始加工工件，[t1,t2]時間段內(nèi)機(jī)器空閑說明t2之后開工的工件(即Bk,Bk+1,…,Bl中的工件)到達(dá)時間均不早于t2，綜合引理1.1得

若t2≤αp1，則Bk必為σ的首批，J1在該批中(否則Bk的開工時間t2至少為p1)，于是P≥p1，下述不等式成立：

情形二 在時間段[t1,t2]內(nèi)機(jī)器在加工某一非Bl的不滿批。

則該批為Bk-1，t1和t2分別為它的開工、完工時間。由于Bk-1是不滿批，根據(jù)算法EF的規(guī)則可知，

t1≥αp1，

(1)

(2)

下面討論2種子情形。

(I)k=2，即Bk-1為σ的首批B1。

(II)k≥3，即σ中Bk-1之前至少有一批加工。

由推論1.1和定理1.2可得以下結(jié)論。

推論1.2 算法EF是在線排序問題

1|on-line,rj,pjnon-increasing,B

的最優(yōu)在線算法。

2 結(jié)論

本文首先證明在線排序問題

1|on-line,rj,pjnon-increasing,B

不存在競爭比小于1+α的在線算法，然后設(shè)計(jì)算法EF,證明該算法是相應(yīng)在線排序問題的最優(yōu)在線算法。

[1]GrahamRL,LawlerEL,LenstraJK,R，etal.Optimizationandapproximationindeterministicsequencingandscheduling[J].AsurveyAnnalsofDiscreteMathematics, 1979， 5(2): 287-326.

[2]DengXT,PoonCK,ZangYZ.Approximationalgorithmsinbatchprocessing[J].JournalofCombinatorialOptimization, 2003, 7: 247-257.

[3]ZhangGC,CaiXQ,WongCK.On-linealgorithmsforminimizingmakespanonbatchprocessingmachines[J].NavalResearchLogistics, 2001, 48: 241-258.

[4]PoonCK,YuWC.Aflexibleon-lineschedulingalgorithmforbatchmachinewithinfinitecapacity[C].Hongkong： 5thConferenceonOptimization:TechniquesandApplication(ICOTA'01), 2001.

[5]PoonCK,YuWC.Aflexibleon-lineschedulingalgorithmforbatchmachinewithinfinitecapacity[J].AnnalsofOperationsResearch, 2005, 133: 175-181.

[6]LiuZH,YuWC.Schedulingonebatchprocessorsubjecttojobreleasedates[J].DiscreteAppliedMaths, 2000, 105: 129-136.

[7]RichardandPQ,RidouardF.On-lineschedulingonasinglebatchingmachinetominimizethemakespan[C].Portugal： 6thInternationalConferenceonIndustrialEngineeringandProductionManagement(IEPM'03)， 2003.

[8] 原晉江, 農(nóng)慶琴. 平行批排序最小化最大完工時間在線算法的一個注記[J]. 鄭州大學(xué)學(xué)報(理學(xué)版), 2006, 38(3): 1-3. Yuan J J, Nong Q Q. A short note on on-line algorithms for single batch machine to minimize makespan [J]. Journal of Zhengzhou University(Natural Science Edition), 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.

[13] Lee C Y, Uzsoy R, Martin Vega L A. Efficient algorithms for scheduling semiconductor burn-in operations [J], Operations Research, 1992, 40: 764-775.

AMS Subject Classification： 90B35

責(zé)任編輯 陳呈超

An Optimal On-Line Algorithm for a Parallel-Batching Scheduling with Non-Increasing Processing Time Jobs

NONG Qing-Qin, MIAO Li-Hui

(School of Mathematical Science, Ocean University of China, Qingdao 266100, China)

In this paper a parallel-batching scheduling to minimize the maximum completion time is considered. There arenjobs to be scheduled on a parallel-batching machine. The 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. Each jobJjhas a processing timepjand a release daterj. Each pair of two jobsJiandJjsatisfies thatpi≥pjifri≤rj. Each job becomes available at its release date. The information of a job, including its release date and its processing time, is unknown until its arrival. The problem involves assigning all the jobs to batches and determining the sequence of batches so as to minimize the makespan (the maximum completion of the jobs). In this paper an optimal on-line algorithms for the problem is designed.

scheduling； parallel-batching； on-line； algorithm； competitive ratio

國家自然科學(xué)基金項(xiàng)目(11201439;11271341)；教育部博士點(diǎn)專項(xiàng)基金新教師基金項(xiàng)目(20120132120001)；山東省自然科學(xué)基金項(xiàng)目(ZR2012AQ12)資助SupportedbytheNationalNaturalScienceFoundationofChinaundergrantnumber11201439and11271341.ThisworkwasalsosupportedinpartbytheDoctoralFundofMinistryofEducationofChina(20120132120001)andbytheShandongProvincialNaturalScienceFoundationundergrandnumberZR2012AQ12

2014-11-25；

2015-10-15

農(nóng)慶琴(1978-)，副教授,博士,研究方向：組合最優(yōu)化。E-mail:qqnong@ouc.edu.cn

O

A

10.16441/j.cnki.hdxb.20140295

農(nóng)慶琴， 苗利輝. 工件加工時間非增的并行分批排序問題的最優(yōu)在線算法[J]. 中國海洋大學(xué)學(xué)報(自然科學(xué)版), 2017, 47(1): 126-130.

NONGQing-Qin,MIAOLi-Hui.AnOptimalon-linealgorithmforaparallel-batchingschedulingwithnon-increasingprocessingtimeJobs[J].PeriodicalofOceanUniversityofChina, 2017, 47(1): 126-130.