Algorithms for Scheduling Tasks on Unrelated Processors

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