Abstract
We consider the multiprocessor scheduling problem in which one must schedule n independent tasks nonpreemptively on m identical, parallel machines, such that the completion time of the last task is minimal. For this well-studied problem the Largest Differencing Method of Karmarkar and Karp outperforms other existing polynomial-time approximation algorithms from an average-case perspective. For m = 3 the worst-case performance of the Largest Differencing Method has remained a challenging open problem. In this paper we show that the worst-case performance ratio is bounded between . For fixed m we establish further refined bounds in terms of n.
Original language | English |
---|---|
Pages (from-to) | 19-32 |
Number of pages | 14 |
Journal | Journal of Combinatorial Optimization |
Volume | 13 |
Issue number | 1 |
DOIs | |
Publication status | Published - 2007 |
Externally published | Yes |