Notes on a hierarchical scheduling problem on identical machines

作者：He, Cheng^*; Lin, Hao

来源：Information Processing Letters, 2017, 120: 6-10.

DOI：10.1016/j.ipl.2016.12.001

• Hierarchical scheduling
• Identical machines
• Total flowtime
• Worst-case ratio
• Approximation algorithms

For the hierarchical scheduling problem on identical machines to minimize the maximum T-time of all machines under the condition that the total completion time of all jobs is minimum, where the T-time of a machine is defined as the total completion time of jobs scheduled on the machine, it is NP-hard if the number of the machines is fixed, and strongly NP-hard otherwise. When the number of the machines is fixed, a forward dynamic programming algorithm and a fully polynomial-time approximation scheme (FPTAS) have been presented in a literature. In the literature, it is showed that the worst-case ratio of the classical algorithm SPT is at most 11/6 and at least 5/3. In this paper, we give an improved worst-case ratio, which is at most 9/5 and at least 7/4, of the algorithm. Another algorithm, whose worst-case ratio is at most 7/6 and at least 35/33, is provided for the two-machine case. On the other hand, we present a backward dynamic programming algorithm and an FPTAS with the better time complexities.

• 出版日期2017-4
• 单位河南工业大学