Total completion time minimization on multiple machines subject to machine availability and makespan constraints

This paper studies preemptive bi-criteria scheduling on m parallel machines with machine unavailable intervals. The goal is to minimize the total completion time subject to the constraint that the makespan is at most a constant T. We study the unavailability model such that the number of available machines cannot go down by 2 within any period of pmax  where pmax  is the maximum processing time among all jobs. We show that there is an optimal polynomial time algorithm.