Preemptive scheduling with release dates, delivery times and sequence independent setup times

This paper deals with the single-machine scheduling problem in which each job has a release date, a processing time and a delivery time. Preemption is permitted and a sequence-independent setup time is incurred before processing a job. The objective is to find a schedule which minimizes the time by which all jobs are delivered. The paper shows that the problem is NP-hard and proposes a heuristic algorithm with a tight worst-case performance bound of and which requires time.