On the exact bounds of SPT for scheduling on parallel machines with availability constraints

This paper considers the scheduling problems with the objective of minimizing the total completion time on two parallel identical machines with given unavailable periods. The jobs are assumed to be nonresumable. If there is one unavailable period on one of the two machines, we prove that SPT has a tight worst-case ratio of 3/2. If there is one unavailable period on each machine, and the unavailable periods on two machines do not overlap, we prove that SPT has a worst-case ratio of 2, which is the smallest possible worst-case ratio that an polynomial time algorithm can have unless P=NP.