Algorithms for Scheduling Tasks on Unrelated Processors
Author(s)
Davis, Ernest; Jaffe, Jeffrey M.![Thumbnail](/bitstream/handle/1721.1/148964/MIT-LCS-TM-137.pdf.jpg?sequence=3&isAllowed=y)
DownloadMIT-LCS-TM-137.pdf (5.032Mb)
Metadata
Show full item recordAbstract
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.
Date issued
1979-06Series/Report no.
MIT-LCS-TM-137