TITLE

ON THE EXACT UPPER BOUND FOR THE MULTIFIT PROCESSOR SCHEDULING ALGORITHM

AUTHOR(S)
Minyi Yue
PUB. DATE
June 1990
SOURCE
Annals of Operations Research;1990, Vol. 24 Issue 1-4, p233
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
We consider 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 [1] described an algorithm, MULTIFTT, 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 [2] that this bound can be improved upon to 1.2. However, we found his proof, in particular his lemma 4.9, difficult to understand. Yue, Kellerer and Yu [3] have presented the bound 1.2 in a simpler way. In this paper, we prove first that the bound cannot exceed 13/11 and then prove that it is exactly 13/11.
ACCESSION #
18656093

 

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics