Approximation algorithms for single-machine sequencing with delivery times and unit batch set-up times

The single machine sequencing problem is considered in which a set of n jobs is divided into batches, each job has a processing time and a delivery time, and there is a unit set-up time associated with switching from jobs in one batch to those in another. The objective is to find a sequence of jobs which minimizes the time by which all jobs are delivered. Three efficient approximation algorithms are described and analyzed. They guarantee worst-case performance bounds of n-1,2 and 5/3.