SINGLE-MACHINE SCHEDULING WITH PROPORTIONALLY DETERIORATING JOBS SUBJECT TO AVAILABILITY CONSTRAINTS

摘要

We address the nonresumable version of the scheduling problem with proportionally deteriorating jobs on a single machine subject to availability constraints. The objective is to minimize the total weighted completion time. We show that there exists no polynomial-time algorithm with a constant worst-case ratio for the problem with two nonavailability intervals unless V = NP. Furthermore, we propose a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for the problem with a single nonavailability interval.