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.
|Number of pages||9|
|Journal||Journal of Scheduling|
|Publication status||Published - 1998|