Worst-case analysis of a scheduling algorithm (Q1060946): Difference between revisions

A heuristic proposed by \textit{O. Ibarra} and \textit{C. Kim} [J. Assoc. Comput. Mach. 24, 280-289 (1977; Zbl 0382.90048)] for scheduling independent tasks on unrelated processors is analyzed. The heuristic may create a schedule which finishes in time m*OPT, where m is the number of processors, and OPT is the time used in the optimal schedule. This compares unfavorably with the heuristics described by \textit{E. Davis} and \textit{J. Jaffe} [ibid. 28, 721-736 (1981; Zbl 0472.68020)], which have worst-case behavior which is \(O(OPT*m^{0.5})\).