运筹学学报 >
2016 , Vol. 20 >Issue 1: 84 - 90
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2016.01.008
提前预知信息的在线分批排序问题
收稿日期: 2015-05-27
网络出版日期: 2016-03-15
基金资助
教育部高等学校博士学科点专项科研基金(No. 20123705110003), 山东省自然科学基金(Nos. ZR2015GZ009, ZR2014AM012), 曲阜师范大学博士科研启动基金(No. bsqd046000051)
Online batch scheduling with known information in advance
Received date: 2015-05-27
Online published: 2016-03-15
研究工件可提前预知信息的在线分批排序问题, 工件的预知信息时间依时间到达, 目标为极小化最大完工时间. 已知从工件的信息可预知到该工件可加工需要时间~$a$, 所有工件的最大加工时间为~$p_{{\rm max}}$, 多个工件可以作为一批被机器同时加工, 批的加工时间为该批工件中最长加工时间. 对于批容量无限的单机问题给出一个在线算法~$\gamma H^\infty$, 并证明其竞争比和问题的下界都为~$1+\gamma$, 其中~$\gamma=\left(-1+\sqrt{1+\frac{4p_{{\rm max}}}{p_{{\rm max}}+a}}\right)/2$, 进而算法是最优的.
王成飞, 张玉忠 . 提前预知信息的在线分批排序问题[J]. 运筹学学报, 2016 , 20(1) : 84 -90 . DOI: 10.15960/j.cnki.issn.1007-6093.2016.01.008
We study a single online batch scheduling problem with known information in advance. The information arrives over time and the objective is to minimize the maximum completion time. The time between the information arrival of a job and its release time is constant $a$. The maximum of the processing times of all jobs $p_{{\rm max}}$ is known in advance too. A batch processing machine can handle up to $b$ jobs simultaneously. The processing time of a batch is given by the longest processing time of all jobs in the batch. When $b=\infty$, we provide an optimal online algorithm $\gamma H^\infty$ with a competitive ratio of $1+\gamma$, where $\gamma=\left(-1+\sqrt{1+\frac{4p_{{\rm max}}}{p_{{\rm max}}+a}}\right)/2$.
Key words： batch scheduling; competitive ratio; online algorithm
[1] Hall N G, Potts C N. Online scheduling with known arrival times [J]. Mathematics of Operations Research, 2009, 34(1): 92-102.
[2] Lee C Y, Uzsoy R. Minimizing makespan on a single batch processing machine with dynamic job arrivals [J]. International Journal of Production Research, 1999, 37(1): 219-236.
[3] Poon C K, Zhang P. Minimizing makespan in batch machine scheduling [J]. Algorithmica, 2004, 39(2): 155-174.
[4] Deng X, Poon C K, Zhang Y. Approximation algorithms in batch scheduling [J]. Journal of Combinatorial Optimization, 2003, 7: 247-257.
[5] Zhang G, Cai X, Wong C K. On-line algorithms for minimizing makespan on batch processing machines [J]. Naval Research Logistics, 2001, 48(3): 241-258.
[6] Tian J, Cheng T C E, Ng C T, et al. Online scheduling on unbounded parallel-batch machines to minimize the makespan [J]. Information Processing Letters, 2009, 109(21-22): 1211-1215.
[7] Liu P, Lu X, Fang Y. A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines [J]. Journal of Scheduling, 2012, 15(1): 77-81.
[8] Kellerer H, Kotov V, Speranza M G, et al. Semi on-line algorithms for the partition problem [J]. Operations Research Letters, 1997, 21: 235-242.
[9] He Y, Zhang G. Semi on-line scheduling on two identical machines [J]. Computing, 1999, 62: 179-187.
[10] Tan Z, He Y. Semi-on-line problems on two identical machines with combined partial information [J]. Operations Research Letters, 2002, 30: 408-414.
[11] Yuan 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.
/
| 〈 |
|
〉 |
