A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs

In this paper we study the NP-hard problem of scheduling n deteriorating jobs on m identical parallel machines to minimize the makespan. Each job's processing time is a linear nondecreasing function of its start time. We present a fully polynomial-time approximation scheme for the problem, thus establishing that the problem is NP-hard in the ordinary sense only.