On the exact upper bound for the MULTIFIT processor scheduling algorithm

On the exact upper bound for the MULTIFIT processor scheduling algorithm

0.00 Avg rating0 Votes
Article ID: iaor19911298
Country: Switzerland
Volume: 24
Start Page Number: 189
End Page Number: 195
Publication Date: Jul 1990
Journal: Annals of Operations Research
Authors:
Abstract:

The paper considers the well-known problem of scheduling n independent tasks nonpreemptively on m identical processors with the aim of minimizing the makespan. Coffman, Garey and Johnson described an algorithm, MULTIFIT, based on techniques from bin-packing, with better worst performance than the LPT algorithm and proved that it satisfies a bound of 1.22. It has been claimed by Friesen that this bound can be improved upon to 1.2. However, his proof, in particular his lemma 4.9, was difficult to understand. Yue, Kellerer and Yu have presented the bound 1.2 in a simpler way. The paper proves first that the bound cannot exceed 13/11 and then proves that it is exactly 13/11.

Reviews

Required fields are marked *. Your email address will not be published.