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

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

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

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

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

排序；并行批；在線；算法；競(jìng)爭(zhēng)比

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

Cmax=max1≤j≤nCj

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

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

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

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

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

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

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

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

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

1 本文主要結(jié)果

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

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

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

算法EF(EarlyFirst)：

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

若0<|U(t)|

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

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

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

定理1.1 對(duì)于1|on-line,rj,B

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

推論1.1 對(duì)于排序問題

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

不存在競(jìng)爭(zhēng)比小于1+α的在線算法。

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

FBLPT(FullBatchLongestProcessingTime)規(guī)則：

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

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

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

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

的競(jìng)爭(zhēng)比為1+α的在線算法。

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

s(B1)

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

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

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

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

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

Bk,Bk+1,…,Bl，

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

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

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

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

則該批為Bk-1，t1和t2分別為它的開工、完工時(shí)間。由于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

不存在競(jìng)爭(zhēng)比小于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)慶琴. 平行批排序最小化最大完工時(shí)間在線算法的一個(gè)注記[J]. 鄭州大學(xué)學(xué)報(bào)(理學(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

國(guó)家自然科學(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)慶琴， 苗利輝. 工件加工時(shí)間非增的并行分批排序問題的最優(yōu)在線算法[J]. 中國(guó)海洋大學(xué)學(xué)報(bào)(自然科學(xué)版), 2017, 47(1): 126-130.

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