李文杰， 马 冉

(1. 洛阳师范学院 数学科学学院 河南 洛阳 471022；2. 河南理工大学 数学与信息科学学院 河南 焦作 454000)

最大化接收工件个数的在线分批排序问题研究

李文杰1， 马 冉2

(1. 洛阳师范学院 数学科学学院 河南 洛阳 471022；2. 河南理工大学 数学与信息科学学院 河南 焦作 454000)

研究m台批处理机上的等长工件在线排序问题. 在该问题中，工件是随着时间依次到达的，每个工件J具有一个共同的加工时间p>0，一个释放时间rj≥0，一个必须交货期dj>0.一台机器可以同时加工b个工件(b个工件构成一批)，b=∞表示批容量无界. 每一批的加工时间由该批中工件的最长加工时间来决定.同一批中的所有工件均具有相同的开工时间和完工时间,目标是确定一个工件可以被中断重启的在线排序最大化接收工件总个数.首先，当m=2、3时分别给出了问题的下界为2和6/5. 其次，设计出了问题的一个在线算法H并证明其竞争比分别为3(当m=2时)、4(当m=3或m≥4为偶数时)和5(当m≥5为奇数时).

在线排序; 在线算法; 批处理机; 竞争比

0 引言

在线排序是现代排序领域中发展最为迅速的研究方向之一.批处理在线排序是一类非常重要的在线排序问题，本文主要是指平行分批(另一种是继列分批)，在不超过批容量b的前提下，一台机器可以同时加工多个工件.批的加工时间由该批中工件的最长加工时间来决定，同一批中的所有工件均具有相同的开工时间和完工时间.在平行分批排序中一般分为两种模型：一种是批容量无界情形(b=)；另一种是批容量有界情形(b<)[1-11].批处理在线环境下的最大化接收工件总利益排序又是近几年学者们持续研究的另一类重要问题，特别是批处理机上等长工件的最大化接收工件总个数的在线排序问题.该问题在网络服务中的一个典型应用是PDD(Pull-based data dissemination)客户服务系统[12-14].

用竞争比来衡量一个在线算法的性能.当工件允许被中断重启时，文献[16]给出了一个竞争比为2的最好可能的在线算法. 文献[17]研究了每个工件都具有相同的加工时间的情形，利用Charging法得到了一个竞争比为3/2的最好可能的在线算法.对工件允许被中断情形，如果每个工件J满足pj=1且dj-rj≥2 时，Goldman等给出了一个3/2竞争的在线算法[18].对于该问题的分批情形，文献[19]用半在线中“lookahead”思想研究该问题.这里的“lookahead”是指任一在线算法在当前时刻t能够预测到在时间段(t,t+l)内，将要到达的所有工件的信息.当0≤l<1时，得到了一个下界min{n,b}，并给出一个简单的在线算法使其竞争比与之匹配,当1≤l<2时，对b=和b<分别给出了问题的下界为2.56和3/2，并且设计了一个批延迟在线算法，并证明该算法的竞争比分别为4(b=时)和5(当b<时).

1 问题的下界

证明 考察任一在线算法A.设ε是一个充分小的正实数并且满足0<ε<1.下面用对手法构造的实例I满足其所有工件均是紧工件，即对任意的J∈I,dj=rj+p.

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

综上，定理1证毕.

2 在线算法H及竞争比分析

第0步: 置t=0.

第1步: 如果U(t)=Φ,则等到有新工件到达，重置t为新工件的到达时刻.

第2步: 如果U(t)≠Φ,并且有机器空闲, 则把U(t)中的工件作为一批在t时刻安排在空闲机器上开始加工.转到第1步.

第3步: 如果U(t)≠Φ,并且所有机器都忙碌，则执行以下运算：

第3.1步: 如果t是机器Mi的一个中断重启点，其中1≤i≤m,则中断Bi(t)并把U(t,i)作为一批在时刻t安排在Mi上开工.转到第1步.

第3.2步: 如果t不是任何机器的一个中断重启点，则重置t∶=min{r,d},其中r是在t之后新工件的到达时刻，d是在t之后机器出现空闲的最早时刻.转到第1步.

假设关于该问题任一实例I中的第一个工件在0时刻到达，最后一个工件在T>0时刻到达.令τ=「T/p⎤. 把时间区间[0,T]划分成a个小区间(其中:如果「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是奇数，其中1≤k≤a,称区间T(k)是一个奇区间，否则就称T(k)是一个偶区间.算法H描述如下：对前⎣m/2」台机器在所有的奇区间T(k)上执行算法H1，1≤k≤a;对后⎣m/2」台机器在所有的偶区间T(k)上执行算法H1; 在剩余的机器以及时间段上，H不做任何决策只需等待.

由算法H可知，在每一个区间T(h)上，其中1≤h≤a,H至多接收⎣m/2」批工件.如果一批工件B在时刻t被安排在Mi上开工， 其中1≤i≤m,并且该批在t′>t时刻被H中断同时H又在时刻t′选择在Mi上开始加工另外一批(记为B′)，称B被B′中断且B是一个由H产生的中断批.可知t′-tW(B). 如果批B′最终被H完全加工称B′是由H产生的一个接收批.分情形讨论算法H的竞争比.

对m=2、3情形，在每一个区间T(k)上，其中1≤k≤a,H至多接收一批工件.不妨设H在T(k)上接收的批为Bk(Bk可能是空集).记Β={Bk:1≤k≤a} 和W(B)=∑J∈Bwj. 则H(I)=W(I). 由于IB中所有工件将会在时刻T+p过期，那么OPT只可能在[0,T)上接收IB的工件. 由算法H可知，对任一时刻点t∈T(k)(1≤k≤a),IB中在t时刻的有效工件集U(t)满足W(U(t))≤W(Bk)，由于OPT关于实例IB最多在T(k)上接收2批工件(对m=2情形)和3批工件(对m=3情形). 因此OPT在T(k)上接收的工件的权和不会超过2W(Bk)(对m=2形)3W(Bk)(对m=3情形). 故有OPT(IB)≤2W(B)(对m=2)OPT(IB)≤3W(B)(对m=3). 另外, OPT(I)≤OPT(IB)+OPT(B). 进一步可得,OPT(I)≤3H(I),当m=2时； OPT(I)≤ 4H(I),当m=3时.

综合以上讨论可得本文的主要结论.

3 结论与展望

[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]刘其佳，张利齐，冯琪. 考虑运输的退化工件在线排序问题研究[J]．郑州大学学报(工学版)，2015，36(2):125-128.

[11]刘其佳，冯琪. 单机上考虑运输的退化工件的在线排序问题[J]．信阳师范学院学报(自然科学版)，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.

(责任编辑：方惠敏)

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

国家自然科学基金资助项目(11501279，11501171); 河南省基础与前沿技术研究计划资助项目(152300410217).

李文杰(1981—)，男，河南正阳人，讲师，博士，主要从事组合数学与最优化研究, E-mail: liwenjie0521@163.com.

李文杰，马冉. 最大化接收工件个数的在线分批排序问题研究[J]. 郑州大学学报(理学版)，2016，48(2)：24-28.

O223

A

1671-6841(2016)02-0024-05

10.13705/j.issn.1671-6841.2015216