Preemptive Scheduling with Due Dates

An 0(n log mn) algorithm is presented to preemptively schedule n tasks on m identical machines. The tasks are assumed to have due dates. All tasks are initially available. The objective is to obtain a preemptive schedule that meets all due dates (when possible). Our algorithm generates schedules with at most n − 2 preemptions. The algorithm may also be used to schedule a set of n tasks all having the same due date but having different release dates.