Rational preemptive scheduling (Q1105366)

Minimum-completion-time preemptive scheduling of jobs on parallel machines subject to precedence constraints that form a partial order is considered. The work is based on the observation that preemptive scheduling by finitely many machines requires only intervals of work, and not a more general assignment of tasks over measurable sets, for optimal completion. It follows that arbitrarily small intervals are not required for a fixed number of machines \(m\geq 3\) for optimal preemptive scheduling. The number of intervals and their length is analyzed for various problem parameters.