Online scheduling on unbounded parallel-batch machines with incompatible job families
Online scheduling on unbounded parallel-batch machines with incompatible job families
复制标题
具有不兼容作业族的无界并行批处理机器上的在线调度
DOI：
10.1016/j.tcs.2011.01.023
复制
发表时间：
2011-05
影响因子：
1.1
通讯作者：
原晋江
中科院分区：
文献类型：
--
作者：
田记;T.C.E. Cheng;C.T. Ng;原晋江
We consider online scheduling on m parallel-batch machines where the batch capacity is unbounded and the jobs belong to m incompatible job families. By incompatible job families, we mean that jobs from different families cannot be processed together in the same batch. The processing time of a job becomes known only upon its arrival. The objective is to minimize the makespan. The problem is difficult to solve so we consider the case where the number of families is equal to the number of machines. We give a lower bound 5+12≈1.618 on the competitive ratio of any online algorithm for this restricted problem. We also provide an online algorithm Hm(θ), where θ∈(0,1) is a parameter, and show that its competitive ratio is no less than 1+105≈1.632. When m=2 or under the condition that jobs belonging to the same family have identical processing times, we show that Hm(α), where α=5−12, is a best possible online algorithm. When m≥3, we prove that Hm(β), where β=2−1, has a competitive ratio no greater than 1+1β+1≈1.707.
登录
查看更多内容
影响因子：
2
作者：
Ruyan Fu;Ji Tian;Jinjiang Yuan
通讯作者：
Ruyan Fu;Ji Tian;Jinjiang Yuan
影响因子：
1
作者：
C. Poon;W. Yu
通讯作者：
C. Poon;W. Yu
DOI：
10.1002/nav.5
发表时间：
2001-04
期刊：
Naval Research Logistics (NRL)
影响因子：
--
作者：
Gouchuan Zhang;Xiaoqiang Cai;C. Wong
通讯作者：
Gouchuan Zhang;Xiaoqiang Cai;C. Wong
影响因子：
9.2
作者：
R. Uzsoy
通讯作者：
R. Uzsoy
DOI：
10.1016/j.orl.2007.01.007
发表时间：
2004-06
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
J. Yuan;Zhaohui Liu;C. T. Ng;T. Cheng
通讯作者：
J. Yuan;Zhaohui Liu;C. T. Ng;T. Cheng