PREEMPTIVE SCHEDULING WITH DUE DATES

An O(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). The algorithm generates schedules with at most n minus 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.