Total completion time minimization scheduling on two hierarchical uniform machines
Total completion time minimization scheduling on two hierarchical uniform machines
复制标题
两台分层统一机器上的总完成时间最小化调度
DOI：
10.1016/j.tcs.2017.08.016
复制
发表时间：
2017-11
影响因子：
1.1
通讯作者：
Zhao Yun
中科院分区：
文献类型：
--
作者：
Zhou Hao;Jiang Yiwei;Zhou Ping;Ji Min;Zhao Yun
This paper investigates an online hierarchical scheduling problem on two uniform machines to minimize the total completion time of all jobs. Machine M 1 with a speed v 1 has a lower hierarchy and machine M 2 with a speed v 2 has a higher hierarchy. Each job has a unit processing time and a hierarchy. The job with a lower hierarchy can only be processed on the machine M 1 and the job with a higher hierarchy can be processed on any of the two machines. We consider two variants of the problem: v 1= 1≤ v 2= s and v 1= s≥ v 2= 1. For both variants, we provide parameter lower bounds and online algorithms with competitive ratio of 9− 41 2 and 33− 3 2 respectively, which are optimal in sense of constant bound.
登录
查看更多内容
单位规模作业在线分层调度中总完成时间最小化
影响因子：
1
作者：
Hu Jueliang;Jiang Yiwei;Zhou Ping;Zhang An;Zhang Qinghui
通讯作者：
Zhang Qinghui
具有两个层次结构的在线并行机调度
影响因子：
1.1
作者：
Jiang, Yiwei;Zhang, An;Tan, Zhiyi
通讯作者：
Tan, Zhiyi
影响因子：
1
作者：
Shlomo Karhi;D. Shabtay
通讯作者：
Shlomo Karhi;D. Shabtay
DOI：
10.1016/j.ic.2007.11.004
发表时间：
2008-05
期刊：
Inf. Comput.
影响因子：
--
作者：
G. Dósa;L. Epstein
通讯作者：
G. Dósa;L. Epstein
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