Scheduling Independent Tasks with Due Times on a Uniform Processor System
Sartaj K. Sahni, Yookun Cho · Journal of the ACM · 1980
An algorithm to preemptively schedule n tasks on m uniform processors is presented.It is assumed that each task is available at time 0. Associated with each task is a due time by which it is to be completed.The algorithm schedules all tasks to complete by their due times whenever possible.The asymptotic time complexity of the algorithm is O(n log n + ran).It generates O(mn) preemptions in the worst case.An example of n tasks requiring O(mn) preemptions is also presented.The algorithm can also be used when all tasks have the same due times but different release times.