Online scheduling of unit length jobs on a batching machine to maximize the number of early jobs with lookahead
Online scheduling of unit length jobs on a batching machine to maximize the number of early jobs with lookahead
复制标题
在配料机上在线调度单位长度作业，以通过前瞻最大限度地提高早期作业的数量
DOI：
10.1016/j.tcs.2009.07.056
复制
发表时间：
2009-11
影响因子：
1.1
通讯作者：
Li, Wenjie
中科院分区：
文献类型：
--
作者：
Cao, Jianfa;Yuan, Jinjiang;Bu, Hailin;Li, Wenjie
本文研究了并行批处理机上单位长度作业的在线调度问题。目标是最大化早期工作的数量。用b表示每个批的大小，其中在无界批中b=∞，在有界批中b<∞。在lkllookforward模型中，在时刻时刻t，在线算法可以预测在时间段（t,t+L）内到达的所有作业。当0≤L<1时，我们证明了一个简单的贪婪在线算法（与L的值无关）具有1/min{n，b+1}的最佳可能竞争比，其中n为作业数。这意味着当0≤L<1时，forward是无用的。当1≤L<2时，我们建立了竞争比的上界0.39（对于b=∞）和2/3（对于b<∞），并给出了竞争比的1/4（对于b=∞）和1/5（对于b<∞）的在线算法。
This paper studies online scheduling of unit length jobs on a parallel batching machine with the help of lookahead. The objective is to maximize the number of early jobs. Denote by b the size of each batch with b=∞ in the unbounded batching and b<∞ in the bounded batching. In the LKLlookahead model, at a time instant t, an online algorithm can foresee all jobs that will arrive in the time segment (t,t+L). When 0≤L<1, we show that a simple greedy online algorithm (independent of the value of L) has a best possible competitive ratio of 1/min{n,b+1}, where n is the number of jobs. This means that lookahead is useless when 0≤L<1. When 1≤L<2, we establish the upper bounds 0.39 (for b=∞) and 2/3 (for b<∞) of competitive ratios, and provide an online algorithm of competitive ratios 1/4 (for b=∞) and 1/5 (for b<∞).
登录
查看更多内容
DOI：
10.1287/moor.1040.0092
发表时间：
2002-01
期刊：
Math. Oper. Res.
影响因子：
--
作者：
E. Anderson;C. Potts
通讯作者：
E. Anderson;C. Potts
DOI：
10.1137/s0097539702403438
发表时间：
2003-03
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Johan Rudin;R. Chandrasekaran
通讯作者：
Johan Rudin;R. Chandrasekaran
DOI：
10.1137/s0895480196296823
发表时间：
2000
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
H. Hoogeveen;Arjen P. A. Vestjens
通讯作者：
H. Hoogeveen;Arjen P. A. Vestjens
影响因子：
--
作者：
UZSOY, R;LEE, CY;MARTINVEGA, LA
通讯作者：
MARTINVEGA, LA
DOI：
10.1016/s0167-6377(00)00061-4
发表时间：
2000-12
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
H. Hoogeveen;C. Potts;G. Woeginger
通讯作者：
H. Hoogeveen;C. Potts;G. Woeginger