Single Machine Scheduling Problems

The single machine case has been the subject of extensive research ever since the early work of Jackson [111] and Smith [180]. In this chapter, we will present algorithms for single machine scheduling problems which are polynomial or pseudopolynomial. It is useful to note the following general result which holds for single machine problems: if all r _j = 0 and if the objective function is a monotone function of the finishing times of the jobs, then only schedules without preemption and without idle time need to be considered. This follows from the fact that the optimal objective value does not improve if preemption is allowed. To see this, consider a schedule in which some job i is preempted, i.e.