A polynomial-time approximation scheme for single-machine sequencing with delivery times and sequence-independent batch set-up times

We investigate the single-machine sequencing problem in which each job has a processing time and a delivery time. The jobs are divided into families and a set-up time is incurred whenever there is a switch from a job in one family to a job in another family. This set-up only depends on the family of the job next to come and hence is sequence independent. The objective to to find a sequence of jobs that minimizes the time by which all jobs are delivered. The best polynomial-time approximation algorithm that was previously known for this problem is due to Zdrzalka and has a worst-case guarantee of 3 2. In this paper, we demonstrate the existence of a polynomial time approximation scheme for the problem.