A linear time approximation scheme for the single machine scheduling problem with controllable processing times

In a scheduling problem with controllable processing times the job processing time can be compressed through incurring an additional cost. We consider the problem of scheduling n jobs on a single machine with controllable processing times. Each job has a release date when it becomes available for processing, and, after completing its processing, requires an additional delivery time. Feasible schedules are further restricted by job precedence constraints. We develop a polynomial time approximation scheme whose running time depends only linearly on the input size. This improves and generalizes the previous (3/2+ɛ)-approximation algorithm by Zdrzalka. Moreover, this linear complexity bound gives a substantial improvement of the best previously known polynomial bound obtained by Hall and Shmoys for the special case without controllable processing times.