Total completion time minimization in online hierarchical scheduling of unit-size jobs
Total completion time minimization in online hierarchical scheduling of unit-size jobs
复制标题
单位规模作业在线分层调度中总完成时间最小化
DOI：
10.1007/s10878-016-0011-2
复制
发表时间：
2016-03
影响因子：
1
通讯作者：
Zhang Qinghui
中科院分区：
文献类型：
--
作者：
Hu Jueliang;Jiang Yiwei;Zhou Ping;Zhang An;Zhang Qinghui
本文研究了m台平行同型机的在线递阶排序问题。我们的目标是最小化所有作业的总完成时间。每个作业都有一个单位处理时间和层次结构。具有较低层次的作业只能在第一台机器上处理，而具有较高层次的作业可以在任何一台机器上处理。我们首先证明这个问题的下界至少是，其中。然后，我们提出了一个贪婪算法的紧竞争比。竞争比是通过分析实例在最坏情况下的结构来获得的，这与最常见的竞争分析方法不同。特别地，当，我们提出了一个最优的在线算法的竞争比，它补充了以前的结果，提供了一个渐近最优算法的竞争比为1.1573的情况下，作业n是无限的，即。
This paper investigates an online hierarchical scheduling problem onmparallel identical machines. Our goal is to minimize the total completion time of all jobs. Each job has a unit processing time and a hierarchy. The job with a lower hierarchy can only be processed on the first machine and the job with a higher hierarchy can be processed on any one ofmmachines. We first show that the lower bound of this problem is at least, where. We then present a greedy algorithm with tight competitive ratio of. The competitive ratio is obtained in a way of analyzing the structure of the instance in the worst case, which is different from the most common method of competitive analysis. In particular, when, we propose an optimal online algorithm with competitive ratio of, which complements the previous result which provided an asymptotically optimal algorithm with competitive ratio of 1.1573 for the case where the number of jobsnis infinite, i.e.,.
登录
查看更多内容
具有两个层次结构的在线并行机调度
影响因子：
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
影响因子：
1
作者：
Yiwei Jiang
通讯作者：
Yiwei Jiang