Best semi-online algorithms for unbounded parallel batch scheduling
Best semi-online algorithms for unbounded parallel batch scheduling
复制标题
无界并行批量调度的最佳半在线算法
DOI：
10.1016/j.dam.2011.01.003
复制
发表时间：
2011-04
影响因子：
1.1
通讯作者：
Cheng, T. C. E.
中科院分区：
文献类型：
--
作者：
Yuan, Jinjiang;Ng, C. T.;Cheng, T. C. E.
我们考虑无界并行批处理机的半在线调度，以最小化完工时间，其中在当前时刻t，t之后到达的第一个最长作业的信息已知。在线表示工件随时间到达，J（t）表示在t之后到达的第一个最长工件，p（t）和r（t）分别表示J（t）的加工时间和到达时间。给定信息p ∈（t），我们给出了一个竞争比为（5−5）/2 ∈ 1.382的在线算法，并证明了该算法是最佳的;此外，该算法最多生成两个批次。该算法也是最佳可能的给定信息J（t）。给出了一个竞争比为3/2的在线算法，并证明了任何在线算法的竞争比都不可能小于33 <$1.442，而且该算法最多生成三个批次.在给定信息r_n（t）的条件下，提出了一个竞争比为（5+1）/2 <$1.618的在线算法，并证明了该算法是最优的.
We consider semi-online scheduling of an unbounded parallel batch machine to minimize the makespan where, at the present time instant t, information on the first longest job arriving after t is known. In this paper online means that jobs arrive over time, J∗(t) denotes the first longest job arriving after t, and p∗(t) and r∗(t) denote the processing time and arrival time of J∗(t), respectively. Given information p∗(t), we present an online algorithm with a competitive ratio (5−5)/2≈1.382, and show that the algorithm is the best possible; furthermore, this algorithm generates at most two batches. This algorithm is also the best possible given information J∗(t). Given information r∗(t), we present an online algorithm with a competitive ratio 3/2, and show that any online algorithm cannot have a competitive ratio less than 33≈1.442; furthermore, this algorithm generates at most three batches. Given information r∗(t) with the restriction that an online algorithm generates at most two batches, we present an online algorithm with a competitive ratio (5+1)/2≈1.618, and show that the algorithm is the best possible.
登录
查看更多内容
DOI：
10.1287/moor.1040.0092
发表时间：
2002-01
期刊：
Math. Oper. Res.
影响因子：
--
作者：
E. Anderson;C. Potts
通讯作者：
E. Anderson;C. Potts
DOI：
10.1137/s0895480196296823
发表时间：
2000
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
H. Hoogeveen;Arjen P. A. Vestjens
通讯作者：
H. Hoogeveen;Arjen P. A. Vestjens
DOI：
10.1016/s0167-6377(00)00053-5
发表时间：
2000-12
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
S. Seiden;J. Sgall;G. Woeginger
通讯作者：
S. Seiden;J. Sgall;G. Woeginger
影响因子：
2.7
作者：
LEE, CY;UZSOY, R;MARTINVEGA, LA
通讯作者：
MARTINVEGA, LA
DOI：
10.1007/3-540-61310-2_30
发表时间：
1996-06
期刊：
--
影响因子：
--
作者：
H. Hoogeveen;Arjen P. A. Vestjens
通讯作者：
H. Hoogeveen;Arjen P. A. Vestjens