最大化接收工件個(gè)數(shù)的在線分批排序問題研究

李文杰， 馬 冉

(1. 洛陽師范學(xué)院 數(shù)學(xué)科學(xué)學(xué)院 河南 洛陽 471022；2. 河南理工大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院 河南 焦作 454000)

最大化接收工件個(gè)數(shù)的在線分批排序問題研究

李文杰1， 馬 冉2

(1. 洛陽師范學(xué)院 數(shù)學(xué)科學(xué)學(xué)院 河南 洛陽 471022；2. 河南理工大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院 河南 焦作 454000)

研究m臺(tái)批處理機(jī)上的等長工件在線排序問題. 在該問題中，工件是隨著時(shí)間依次到達(dá)的，每個(gè)工件J具有一個(gè)共同的加工時(shí)間p>0，一個(gè)釋放時(shí)間rj≥0，一個(gè)必須交貨期dj>0.一臺(tái)機(jī)器可以同時(shí)加工b個(gè)工件(b個(gè)工件構(gòu)成一批)，b=∞表示批容量無界. 每一批的加工時(shí)間由該批中工件的最長加工時(shí)間來決定.同一批中的所有工件均具有相同的開工時(shí)間和完工時(shí)間,目標(biāo)是確定一個(gè)工件可以被中斷重啟的在線排序最大化接收工件總個(gè)數(shù).首先，當(dāng)m=2、3時(shí)分別給出了問題的下界為2和6/5. 其次，設(shè)計(jì)出了問題的一個(gè)在線算法H并證明其競爭比分別為3(當(dāng)m=2時(shí))、4(當(dāng)m=3或m≥4為偶數(shù)時(shí))和5(當(dāng)m≥5為奇數(shù)時(shí)).

在線排序; 在線算法; 批處理機(jī); 競爭比

0 引言

在線排序是現(xiàn)代排序領(lǐng)域中發(fā)展最為迅速的研究方向之一.批處理在線排序是一類非常重要的在線排序問題，本文主要是指平行分批(另一種是繼列分批)，在不超過批容量b的前提下，一臺(tái)機(jī)器可以同時(shí)加工多個(gè)工件.批的加工時(shí)間由該批中工件的最長加工時(shí)間來決定，同一批中的所有工件均具有相同的開工時(shí)間和完工時(shí)間.在平行分批排序中一般分為兩種模型：一種是批容量無界情形(b=)；另一種是批容量有界情形(b<)[1-11].批處理在線環(huán)境下的最大化接收工件總利益排序又是近幾年學(xué)者們持續(xù)研究的另一類重要問題，特別是批處理機(jī)上等長工件的最大化接收工件總個(gè)數(shù)的在線排序問題.該問題在網(wǎng)絡(luò)服務(wù)中的一個(gè)典型應(yīng)用是PDD(Pull-based data dissemination)客戶服務(wù)系統(tǒng)[12-14].

用競爭比來衡量一個(gè)在線算法的性能.當(dāng)工件允許被中斷重啟時(shí)，文獻(xiàn)[16]給出了一個(gè)競爭比為2的最好可能的在線算法. 文獻(xiàn)[17]研究了每個(gè)工件都具有相同的加工時(shí)間的情形，利用Charging法得到了一個(gè)競爭比為3/2的最好可能的在線算法.對(duì)工件允許被中斷情形，如果每個(gè)工件J滿足pj=1且dj-rj≥2 時(shí)，Goldman等給出了一個(gè)3/2競爭的在線算法[18].對(duì)于該問題的分批情形，文獻(xiàn)[19]用半在線中“l(fā)ookahead”思想研究該問題.這里的“l(fā)ookahead”是指任一在線算法在當(dāng)前時(shí)刻t能夠預(yù)測(cè)到在時(shí)間段(t,t+l)內(nèi)，將要到達(dá)的所有工件的信息.當(dāng)0≤l<1時(shí)，得到了一個(gè)下界min{n,b}，并給出一個(gè)簡單的在線算法使其競爭比與之匹配,當(dāng)1≤l<2時(shí)，對(duì)b=和b<分別給出了問題的下界為2.56和3/2，并且設(shè)計(jì)了一個(gè)批延遲在線算法，并證明該算法的競爭比分別為4(b=時(shí))和5(當(dāng)b<時(shí)).

1 問題的下界

證明 考察任一在線算法A.設(shè)ε是一個(gè)充分小的正實(shí)數(shù)并且滿足0<ε<1.下面用對(duì)手法構(gòu)造的實(shí)例I滿足其所有工件均是緊工件，即對(duì)任意的J∈I,dj=rj+p.

情形1n1=n2=N或N=n1

綜上，定理1證畢.

2 在線算法H及競爭比分析

第0步: 置t=0.

第1步: 如果U(t)=Φ,則等到有新工件到達(dá)，重置t為新工件的到達(dá)時(shí)刻.

第2步: 如果U(t)≠Φ,并且有機(jī)器空閑, 則把U(t)中的工件作為一批在t時(shí)刻安排在空閑機(jī)器上開始加工.轉(zhuǎn)到第1步.

第3步: 如果U(t)≠Φ,并且所有機(jī)器都忙碌，則執(zhí)行以下運(yùn)算：

第3.1步: 如果t是機(jī)器Mi的一個(gè)中斷重啟點(diǎn)，其中1≤i≤m,則中斷Bi(t)并把U(t,i)作為一批在時(shí)刻t安排在Mi上開工.轉(zhuǎn)到第1步.

第3.2步: 如果t不是任何機(jī)器的一個(gè)中斷重啟點(diǎn)，則重置t∶=min{r,d},其中r是在t之后新工件的到達(dá)時(shí)刻，d是在t之后機(jī)器出現(xiàn)空閑的最早時(shí)刻.轉(zhuǎn)到第1步.

假設(shè)關(guān)于該問題任一實(shí)例I中的第一個(gè)工件在0時(shí)刻到達(dá)，最后一個(gè)工件在T>0時(shí)刻到達(dá).令τ=「T/p?. 把時(shí)間區(qū)間[0,T]劃分成a個(gè)小區(qū)間(其中:如果「T/p?=T/p,a=τ+1; 否則a=τ)，T(1)=[0,p),…,T(a-1)=[(a-2)p,(a-1)p),如果a=τ,T(a)=[(a-1)p,T)，否則T(a)=[T,).如果k是奇數(shù)，其中1≤k≤a,稱區(qū)間T(k)是一個(gè)奇區(qū)間，否則就稱T(k)是一個(gè)偶區(qū)間.算法H描述如下：對(duì)前?m/2」臺(tái)機(jī)器在所有的奇區(qū)間T(k)上執(zhí)行算法H1，1≤k≤a;對(duì)后?m/2」臺(tái)機(jī)器在所有的偶區(qū)間T(k)上執(zhí)行算法H1; 在剩余的機(jī)器以及時(shí)間段上，H不做任何決策只需等待.

由算法H可知，在每一個(gè)區(qū)間T(h)上，其中1≤h≤a,H至多接收?m/2」批工件.如果一批工件B在時(shí)刻t被安排在Mi上開工， 其中1≤i≤m,并且該批在t′>t時(shí)刻被H中斷同時(shí)H又在時(shí)刻t′選擇在Mi上開始加工另外一批(記為B′)，稱B被B′中斷且B是一個(gè)由H產(chǎn)生的中斷批.可知t′-tW(B). 如果批B′最終被H完全加工稱B′是由H產(chǎn)生的一個(gè)接收批.分情形討論算法H的競爭比.

對(duì)m=2、3情形，在每一個(gè)區(qū)間T(k)上，其中1≤k≤a,H至多接收一批工件.不妨設(shè)H在T(k)上接收的批為Bk(Bk可能是空集).記Β={Bk:1≤k≤a} 和W(B)=∑J∈Bwj. 則H(I)=W(I). 由于IB中所有工件將會(huì)在時(shí)刻T+p過期，那么OPT只可能在[0,T)上接收IB的工件. 由算法H可知，對(duì)任一時(shí)刻點(diǎn)t∈T(k)(1≤k≤a),IB中在t時(shí)刻的有效工件集U(t)滿足W(U(t))≤W(Bk)，由于OPT關(guān)于實(shí)例IB最多在T(k)上接收2批工件(對(duì)m=2情形)和3批工件(對(duì)m=3情形). 因此OPT在T(k)上接收的工件的權(quán)和不會(huì)超過2W(Bk)(對(duì)m=2形)3W(Bk)(對(duì)m=3情形). 故有OPT(IB)≤2W(B)(對(duì)m=2)OPT(IB)≤3W(B)(對(duì)m=3). 另外, OPT(I)≤OPT(IB)+OPT(B). 進(jìn)一步可得,OPT(I)≤3H(I),當(dāng)m=2時(shí)； OPT(I)≤ 4H(I),當(dāng)m=3時(shí).

綜合以上討論可得本文的主要結(jié)論.

3 結(jié)論與展望

[1] MATHIRAJAN M, SIVAKUMAR A I. A literature review, classification and simple metaanalysis on scheduling of batch processors in semiconductor[J]. International journal of advanced manufacturing technology, 2006, 29(9): 990-1001.

[2] ALLAHVERDI A, NG C T, CHENG T C E, et al. A survey of scheduling problems with setup times or costs[J]. European journal of operational research, 2008, 187(3):985-1032.

[3] WEBSTER S T, BAKER K R. Scheduling groups of jobs on a single machine[J]. Operations research, 1995, 43(4): 692-703.

[4] 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(3): 241-258.

[5] ZHANG G C, CAI X Q, WONG C K. Online algorithms for scheduling on parallel batch processing machines[J]. IIE transations, 2003, 35(2):175-181.

[6] DOBSON G, NAMBIMADOM R S. The batch loading and scheduling problem[J]. Operations research, 2001, 49(1): 52-65.

[7] YUAN J J, Ng C T, CHENG T C E. Best semi-online algorithms for unbounded parallel batch scheduling[J]. Discrete applied mathematics, 2011, 159(8): 838-847.

[8] LI W H, YUAN J J. Online scheduling on unbounded parallel-batch machines to minimize maximum flow-time[J]. Information processing letters, 2011, 111(8):907-911.

[9] TIAN Ji, FU R Y, YUAN J J. Online over time scheduling on parallel-batch machines: a survey[J]. Operations research society of China, 2014, 2(4):445-454.

[10]劉其佳，張利齊，馮琪. 考慮運(yùn)輸?shù)耐嘶ぜ诰€排序問題研究[J]．鄭州大學(xué)學(xué)報(bào)(工學(xué)版)，2015，36(2):125-128.

[11]劉其佳，馮琪. 單機(jī)上考慮運(yùn)輸?shù)耐嘶ぜ脑诰€排序問題[J]．信陽師范學(xué)院學(xué)報(bào)(自然科學(xué)版)，2015，28(2):157-159.

[12]KALYANASUNDARAM B, VELAUTHAPILLAI M. On-demand broadcasting under deadline[J]. Springer Berlin heidelberg, 2003,2382: 313-324.

[13]SHARAF M A, CHRYSANTHIS P K. On-demand data broadcasting for mobile decision making[J]. Mobile networks and applications, 2004, 9(6):703-714.

[14]HUNG R Y S, TING H F. Design and analysis of online batching systems[J]. Algorithmica, 2010, 57(2):217-231.

[15]GRAHAM R L, LAWER E L, LENSTRA J K, et al. Optimization and approximation in deterministic sequencing and scheduling[J]. Annals of discrete mathematics, 1979, 5:287-326.

[16]HOOGEVEEN H, POTTS C N, WOEGINGER G J. On-line scheduling on a single machine: maximizing the number of early jobs[J]. Operations research letters, 2000, 27(5):193-196.

[17]CHROBAK M, JAWOR W, SGALL J, et al. Online scheduling of equal-length jobs: randomization and restarts help[J]. Springer Berlin heidelberg, 2013, 3142(6):358-370.

[18]GOLDMAN S A, PARWATIKAR J, SURI S. Online scheduling with hard deadlines[J]. Journal of algorithms, 2000, 34(2): 370-389.

[19]LI W J, YUAN J J, CAO J F, et al. Online scheduling of unit length jobs on a parallel batching machineto maximize the number of early jobs with lookahead[J]. Theoretical computer science, 2009, 410(47/49): 5182-5187.

[20]FUNG S P Y, POON C K, ZHENG F F. Online interval scheduling: randomized and multiprocessor cases[J]. International conference on computing and combination, 2007, 16(3): 248-262.

[21]LI WJ, YUAN J J. Improved online algorithms for the batch scheduling of equal-length jobs with incompatible families to maximize the weighted number of early jobs[J]. Optimization Letters, 2013,8(5):1691-1706.

(責(zé)任編輯：方惠敏)

Research on the Online Batch Scheduling to Maximize Total Number of the Accepted Jobs

LI Wenjie1, MA Ran2

(1.SchoolofMathematicalSciences,LuoyangNormalUniversity,Luoyang471022,China;2.SchoolofMathematicsandInformationScience,HenanPolytechnicUniversity,Jiaozuo454000,China)

The online scheduling of equal-length jobs was studied onmidentical batch machines. In this problem, jobs arrive over time and each job needed a common processing timep>0, a release timerj≥0, a deadlinedj>0. Each batch machine can process up to b jobs simultaneously as a batch. “b=∞” means that the capacity of batch was unbounded. The goal was to determine a preemption-restart schedule which maximizes the total number of the accepted jobs. A lower bound of 2 form=2 and 6/5 form=3, was presented respectively. An online algorithmHwas provided with a competitive ratio of 3 (whenm=2), 4(whenm=3 orm≥4 is even), 5(whenm≥5 is odd), respectively.

online scheduling; online algorithm; batch machines; competitive ratio

2015-10-07

國家自然科學(xué)基金資助項(xiàng)目(11501279，11501171); 河南省基礎(chǔ)與前沿技術(shù)研究計(jì)劃資助項(xiàng)目(152300410217).

李文杰(1981—)，男，河南正陽人，講師，博士，主要從事組合數(shù)學(xué)與最優(yōu)化研究, E-mail: liwenjie0521@163.com.

李文杰，馬冉. 最大化接收工件個(gè)數(shù)的在線分批排序問題研究[J]. 鄭州大學(xué)學(xué)報(bào)(理學(xué)版)，2016，48(2)：24-28.

O223

A

1671-6841(2016)02-0024-05

10.13705/j.issn.1671-6841.2015216