Algorithms for Scheduling Tasks on Unrelated Processors

Abstract

Several algorithms are presented for the nonpreemptive assignment of n independent tasks to m unrelated processors. One algorithm requires polynomial time in n and m, and is at most 2√m 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 time in m. This is the best algorithm known that requires time O(nlog(n)) for every fixed value of m.