Structural properties of optimal schedules with preemption

Scheduling problems with preemption are considered, where each operation can be interrupted and resumed later without any penalty. We investigate some basic properties of their optimal solutions, such as the existence of an optimal schedule (provided that the set of feasible solutions is nonempty), the existence of such a solution with a finite/polynomial number of interruptions or with interruptions at integral points only. 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 provide answers to these basic questions for a rather general scheduling model (including, as its special cases, such classical models as parallel machine scheduling, shop scheduling, and resource constrained project scheduling) and for a large variety of objective functions, including nearly all known. For two special cases of objective functions (including, however, all classical functions) we prove the existence of an optimal solution with a special “rational structure”. An important consequence of this property is that the decision versions of these optimization scheduling problems belong to class NP. Bibl. 13.