Algorithms for Scheduling Tasks on Unrelated Processors
Ernest Davis, Jeffrey M. Jaffe · Journal of the ACM · 1981
Several algorithms are presented for the nonpreemptlve assignment of n independent tasks to m unrelated processors One algorithm requires polynomial Ume in n and m and IS at most 2x/~ times worse than optimal in the worst case This is the best polynomial-time algorithm known for scheduling such sets of tasks.An algorithm with slightly better worst case performance requires polynomial time in n but exponential ume in m This 1s the best algorithm known that requires time O(nlogn) for every fixed value of m KEY WORDS AND PHRASES nonpreemptlve schedules, worst case fimshlng time, performance ratio, unrelated processors, largest processing time CR CATEGORIES' 4 32, 4 35, 5 25, 5 39 IntroductzonThis paper presents a number of polynomial-time algorithms for the scheduling of a set of n independent tasks on m processors of different speeds.The processors are unrelated in the sense that there is no notion of a fast processor always requiring less time than a slow processor, irrespective of the task being executed.Rather, the time required for the execution of a task on a processor is a function of both the task and the processor.This models the situation in which general-purpose processors have specialized capabilities that permit them to execute certain tasks more efficiently than others.An example of this might be in a distributed system where the time requirement of a task on a processor may depend on communication costs.The decision problem of determining whether a given set of tasks can be assigned with finishing time smaller than a given bound is NP-complete [6].As a result, it seems unlikely that an algorithm can be found which runs m polynomial time and always produces the optimal assignment [3].It is thus worthwhile to investigate approximation algorithms.