An FPTAS for batch scheduling with deterioration effect

This paper considers scheduling linear deteriorating jobs on a single machine. The jobs are processed in batches and the objective is to minimize the makespan. Linear deterioration effect means that job´s actual processing time is a linear increasing function on its waiting time, i.e., the time between the execution of the batch to which the job belongs and the job´s starting time. We propose a fully polynomial-time approximation scheme (FPTAS) to show the problem is NP-hard in the ordinary sense.