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 p max where p max is the maximum processing time among all jobs. We show that there is an optimal polynomial time algorithm. 
Total completion time minimization on multiple machines subject to machine availability and makespan constraints