Structural Properties of Preemptive Schedules

Consider some preemptive scheduling problem, i.e., a problem where we can inter-rupt operations and resume them later without any penalties. What can we say about the optimal schedule? When does the optimal schedule exist? When does it have a limited (polynomial) number of interruptions? Do they occur at integer time points? Such theoretical questions are also of practical interest since structural properties can be used to reduce the search space in a practical scheduling application. In this paper we answer these questions for a large variety of scheduling models, including parallel machine scheduling, shop scheduling and resource constrained project scheduling