Scheduling resumable deteriorating jobs on a single machine with non-availability constraints
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 P = NP. (c) 2010 Elsevier B.V. All rights reserved.
scheduling deteriorating job non-availability constraint fully polynomial-time approximation scheme