Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

List scheduling algorithms to minimize the makespan on identical parallel machines

  • Published:
Top Aims and scope Submit manuscript

Abstract

In this paper we present constructive algorithms for the classical deterministic scheduling problem of minimizing the makespan on identical machines. Since the problem is known to beNP-hard in the strong sense, the approximate algorithms play a relevant role when solving this problem. The proposed algorithms are based on list scheduling procedures, but the assignment rule is not the same for the full set of jobs. Computational results show that these algorithms perform very well.

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

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Similar content being viewed by others

References

  • Achugbue J.O. and Chin F.Y. (1981). Bounds on schedules for independent tasks with similar execution time.Journal of the Association for Computing Machinery 28, 81–99.

    Google Scholar 

  • Arora S. and Lund C. (1997). Hardness of Approximations. In: Hochbaum D.S. (ed.),Approximation Algorithms for NP-hard Problems. PWS, 399–446.

  • Coffman E.G. Jr., Garey M.R. and Johnson D.S. (1978). An application of Bin-Packing to multiprocessor scheduling.SIAM Journal on Computing 7, 1–17.

    Article  Google Scholar 

  • Cook S.A. (1971). The complexity of theorem-proving procedures.Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 151–158.

  • De P. and Morton T.E. (1980). Scheduling to minimum makespan on unequal parallel processors.Decision Science 11, 586–602.

    Google Scholar 

  • Dobson G. (1984). Scheduling independent tasks on uniform processors.SIAM Journal of Computing 13, 705–716.

    Article  Google Scholar 

  • França P.M., Gendreau M., Laporte G. and Müller F.M. (1994). A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective.Computers and Operations Research 21, 205–210.

    Article  Google Scholar 

  • Frenk J. and Rinnooy Kan A.H.G. (1984a). The asymptotic optimality of the LPT scheduling heuristic. Report, Erasmus University, Rotterdam.

    Google Scholar 

  • Frenk J. and Rinnooy Kan A.H.G. (1984b). The rate of convergence to optimality of the LPT scheduling heuristic. Report, Erasmus University, Rotterdam.

    Google Scholar 

  • Graham R.L. (1966). Bounds for certain multiprocessing anomalies.Bell System Technical Journal 45, 1563–1581.

    Google Scholar 

  • Graham R.L. (1969). Bounds on multiprocessing timing anomalies.SIAM Journal on Applied Mathematics 17, 263–269.

    Google Scholar 

  • Graham R.L., Lawler E.L., Lenstra J.K. and Rinnooy Kan A.H.G. (1979). Optimization and approximation in deterministic sequencing and scheduling. A survey.Annals of Discrete Mathematics 5, 287–326.

    Article  Google Scholar 

  • Han S., Hong D. and Leung J.Y.T. (1995). On the asymptotic optimality of multiprocessor scheduling heuristics for the makespan minimization problem.ORSA Journal on Computing 2, 201–204.

    Google Scholar 

  • Haupt R. (1989). A survey of priority rule-based scheduling.Operational Research Spektrum 11, 3–16.

    Article  Google Scholar 

  • Hübscher R. and Glover F. (1994). Applying Tabu Search with influential diversification to multiprocessor scheduling.Computers Operations Research 8, 877–884.

    Article  Google Scholar 

  • Ibarra O.H. and Kim C.E. (1976). On two processor scheduling of one-or two-unit time tasks with precedence constraints.Journal of Cybernetics 5, 87–109.

    Google Scholar 

  • Karp R.M. (1972). Reducibility among combinatorial problems. In: Miller R.E. and Tatcher J.W. (eds.),Complexity of Computer Computations. Plenum Press, 85–103.

  • Lenstra J.K. and Rinnooy Kan A.H.G. (1979). Computational complexity of discrete optimization. In: Lenstra J.K., Rinnooy Kan A.H.G. and Van Emde Boas P. (eds.),Interfaces Between Computer Science and Operations Research. Proceedings of a Symposium held at the Matematisch Centrum, Amsterdam, 64–85.

  • Lenstra J.K. and Shmoys D.B. (1995). Computing near-optimal schedules. In: Chrétienne P., Coffman E.G. Jr., Lenstra J.K. and Liu Z. (eds.),Scheduling Theory and its Applications. Wiley, 1–14.

  • McNaughton R. (1959). Scheduling with deadlines and loss function.Management Science 6, 1–12.

    Google Scholar 

  • Mokotoff E. (1998). Metodologías de Resolución de Problemas de Asignación y Ordenación de Tareas a Recursos: Planificación con Recursos Idénticos (in Spanish). PhD Thesis, Universidad de Alcalá.

  • Mokotoff E. (1999). Scheduling to Minimize the Makespan on Identical Parallel Machines: An LP-Based Algorithm.Investigación Operativa 8, 97–108.

    Google Scholar 

  • Mokotoff E. (2001). Parallel Machine Scheduling Problems: A Survey.Asia-Pacific Journal of Operational Research 18, 193–243.

    Google Scholar 

  • Panwalkar S.S. and Iskander W. (1977). A survey of scheduling rules.Operations Research 25, 45–61.

    Article  Google Scholar 

  • Riera J., Alcaide D. and Sicilia J. (1996). Approximate algorithms for theP//C max problem.Top 4, 345–359.

    Article  Google Scholar 

  • Sahni S. (1977). General techniques for combinatorial optimization.Operations Research 25, 920–936.

    Google Scholar 

  • Sotskov Y.N. and Shaklevich N.V. (1995). NP-hardness of shop scheduling problems with three jobs.Discrete Applied Mathematics 59, 237–266.

    Article  Google Scholar 

  • Weiss G. (1995). On almost optimal priority rules for preemptive scheduling of stochastic jobs on parallel machines.Advances in Applied Probability 27, 821–839.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Additional information

This research has been partially supported by the Research Project H015/2000, Universidad de Alcalá. The authors are indebted to Joaquín Pérez and the referees for their helpful remarks and comments. We also wish to thank Paul Alexander Ayres for his help in the correct use of English.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mokotoff, E., Jimeno, J.L. & Gutiérrez, A.I. List scheduling algorithms to minimize the makespan on identical parallel machines. Top 9, 243–269 (2001). https://doi.org/10.1007/BF02579085

Download citation

  • Received:

  • Accepted:

  • Issue Date:

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

Key Words

AMS subject classification

Navigation