Primary–secondary bicriteria scheduling on identical machines to minimize the total completion time of all jobs and the maximum T-time of all machines

In this paper, we study a new primary–secondary bicriteria scheduling problem on identical machines. The primary objective is to minimize the total completion time of all jobs and the secondary objective is to minimize the maximum T-time of all machines, where the T-time of a machine is defined as the total completion time of the jobs scheduled on the machine. The problem is to find a non-preemptive schedule of minimizing the secondary objective subject to the constraint that the primary objective is minimized. It is implied in the literature that the problem is ordinarily NP-hard if the number of machines is fixed, and strongly NP-hard if the number of machines is a part of input. When the number of machines is fixed, we present a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme. Then we analyze the classic algorithm SPT which schedules jobs to machines greedily in the order of non-decreasing processing times. We show that the worst-case ratio of SPT is of at most 11/6 and at least 5/3. Furthermore, we present another algorithm, called RSPT, with the worst-case ratio of at most 3/2 and at least 11/9.