Scheduling resumable deteriorating jobs on a single machine with non-availability constraints

Abstract: We consider a problem of scheduling resumable deteriorating jobs on a single machine with non-availability constraints. The objective is to minimize the total completion time. We prove that the problem with a single non-availability period is NP-hard in the ordinary sense and possesses a fully polynomial-time approximation scheme. In addition, we show that there does not exist a polynomial-time approximation algorithm with a constant worst-case ratio for the problem with two or more non-availability periods, unless . [ABSTRACT FROM AUTHOR]