Minimizing Total Completion Time Subject to Job Release Dates and Preemption Penalties

Extensive research has been devoted to preemptive scheduling. However, little attention has been paid to problems where a certain time penalty must be incurred if preemption is allowed. In this paper, we consider the single-machine scheduling problem of minimizing the total completion time subject to job release dates and preemption penalties, where each time a job is started, whether initially or after being preempted, a job-independent setup must take place. The problem is proved to be strongly NP-hard even if the setup time is one unit. We also study a natural extension of a greedy algorithm, which is optimal in the absence of preemption penalty. It is proved that the algorithm has a worst-case performance bound of 25/16, even when the maximum completion time, i.e., makespan, criterion is considered simultaneously.