Online parallel machines scheduling with two hierarchies
Online parallel machines scheduling with two hierarchies
复制标题
具有两个层次结构的在线并行机调度
DOI：
10.1016/j.tcs.2009.04.007
复制
发表时间：
2009-09
影响因子：
1.1
通讯作者：
Tan, Zhiyi
中科院分区：
文献类型：
--
作者：
Jiang, Yiwei;Zhang, An;Tan, Zhiyi
本文研究了m台平行同型机的在线递阶排序问题。每个作业以及每台机器都有一个与之关联的层次结构。只有当作业的层次结构不高于机器的层次结构时，才能在机器上调度作业。目标是最小化最大完工时间。此外，我们假设只有两个层次，和k台机器有一个更高的层次，可以调度所有的作业。我们提出了一个在线算法，对于任何k和m，竞争比为1+m2−mm2−km+k2<73。通过另一种算法进一步提高了某些k和m对的性能。还提出了各种对k和m的下界。
This paper investigates an online hierarchical scheduling problem on m parallel identical machines. Each job, as well as each machine, has a hierarchy associated with it. A job can be scheduled on a machine only when its hierarchy is no higher than that of the machine. The objective is to minimize the makespan. In addition, we assume that there are only two hierarchies, and k machines have a higher hierarchy which can schedule all jobs. We present an online algorithm with a competitive ratio of 1+m2−mm2−km+k2<73 for any k and m. The performance for some pairs of k and m is further improved by another algorithm. Lower bounds for various pairs of k and m are also presented.
登录
查看更多内容
DOI：
10.1137/s0097539702403438
发表时间：
2003-03
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Johan Rudin;R. Chandrasekaran
通讯作者：
Johan Rudin;R. Chandrasekaran
DOI：
10.1002/nav.20202
发表时间：
2007-04
期刊：
Naval Research Logistics (NRL)
影响因子：
--
作者：
C. Glass;H. Kellerer
通讯作者：
C. Glass;H. Kellerer
影响因子：
2
作者：
R. Fleischer;Michael G. Wahl
通讯作者：
R. Fleischer;Michael G. Wahl
DOI：
10.1016/s0305-0548(03)00164-3
发表时间：
2004-10
期刊：
Comput. Oper. Res.
影响因子：
--
作者：
H. Hwang;Soo Y. Chang;Kangbok Lee
通讯作者：
H. Hwang;Soo Y. Chang;Kangbok Lee
DOI：
10.1016/s0166-218x(03)00341-x
发表时间：
2004-03
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
P. Crescenzi;G. Gambosi;P. Penna
通讯作者：
P. Crescenzi;G. Gambosi;P. Penna