Notes on a hierarchical scheduling problem on identical machines

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 116 and at least 53. In this paper, we give an improved worst-case ratio, which is at most 95 and at least 74, of the algorithm. Another algorithm, whose worst-case ratio is at most 76 and at least 3533, 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.