Skip to main content
SpringerLink
Log in

On the exact upper bound for the multifit processor scheduling algorithm

  • Methodology
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

We consider the well-known problem of schedulingn independent tasks nonpre-emptively onm identical processors with the aim of minimizing the makespan. Coffman, Garey and Johnson [1] described an algorithm, MULTIFIT, based on techniques from binpacking, 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. E.G. Coffman, M.R. Garey and D.S. Johnson, An application of bin-packing to multiprocessor scheduling, SIAM J. Comput. 7(1978)1–17.

    Google Scholar 

  2. D.K. Friesen, Tighter bounds for the MULTIFIT processor scheduling algorithm, SIAM J. Comput. 13(1984)179–181.

    Google Scholar 

  3. M. Yue, H. Kellerer and Z. Yu, A simple proof of the inequalityR M (MF(k))≤1.2+1/2k in multiprocessor scheduling, Report No. 124, Institut für Mathematik, Technische Universität Graz (1988), pp. 1–10.

  4. E.G. Coffman, Jr., etal., Approximation algorithms for bin-packing—an updated survey, in:Algorithm Design and Computer System Design, ed. G. Ausiello et al., CISM Courses and Lectures 284 (Springer, Vienna), pp. 49–106.

Download references

Author information

Authors and Affiliations

  1. Institute of Applied Mathematics, Academia Sinica, 100080, Beijing, P.R. China

    Minyi Yue

Authors
  1. Minyi Yue
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work was done while the author was visiting the Institut für Operations Research, Universität Bonn. The author expresses his thanks to the Institut for the support given to him in the preparation and completion of the work.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Yue, M. On the exact upper bound for the multifit processor scheduling algorithm. Ann Oper Res 24, 233–259 (1990). https://doi.org/10.1007/BF02216826

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02216826

Keywords

Search

Navigation