×

Tighter bounds for the MULTIFIT processor scheduling algorithm. (English) Zbl 0539.68024

This paper presents the problem of nonpreemptively scheduling n independent tasks on m identical parallel processors to minimize the completion time for the entire set of tasks. For obtaining the optimal schedule in this case, M. R. Garey, E. G. Coffman jun., and D. S. Johnson [SIAM J. Comput. 7, 1-17 (1978; Zbl 0374.68032)] showed an algorithm MULTIFIT which has a considerably better worst case performance than the largest processing time (LPT) first algorithm. The purpose of the present paper is to tighten the bounds obtained in that paper on the worst case behavior of algorithm MULTIFIT by giving an example showing that it may be as bad as 13/11 and proving that it can be no worse than 6/5.
Reviewer: J.Martyna

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B35 Deterministic scheduling theory in operations research

Citations:

Zbl 0374.68032
Full Text: DOI