How small are shifts required in optimal preemptive schedules?

An event in a schedule is a job start, interruption, resumption or completion time. A shift in a schedule is an non-idling interval between two events that does not contain other events. If a scheduling problem with a regular criterion has only integer data (and we consider here only such problems), then the length of smallest shifts required in optimal nonpreemptive schedules is obviously 1. The length of smallest shifts required in optimal preemptive schedules, however, can be infinitely small. As Sauer and Stone (Order 4:195–206, 1987) showed more than 25 years ago, shifts of length less than (Formula presented.) are not required in shortest preemptive schedules of (Formula presented.) unit-length jobs with precedence constraints on (Formula presented.) identical parallel machines. They showed, on the other hand, that there are instances for infinitely many (Formula presented.) such that shifts of length less than (Formula presented.) can be required if (Formula presented.). In this paper, we continue research in the same direction and strengthen their results, finding the respective tighter bounds, (Formula presented.) and (Formula presented.). We also obtain similar results for other preemptive scheduling problems on identical parallel machines. A useful consequence of certain of these results is that preemptive scheduling problems with unequal release dates and/or unequal due dates can require even smaller shifts for optimality. We also identify problems whose optimal preemptive schedules do not require shifts of length less than (Formula presented.).Department of Logistics and Maritime Studie