Comparison of Heuristics for Identical Parallel Machine Scheduling

Abstract:

This paper addresses the problem of scheduling n independent jobs processed nonpreemtively on m identical parallel machines with the objective of minimizing makespan. Since these scheduling problems are well known to be NP-hard, among various solution methodologies, heuristics are preferred most. They guarantee near-optimal solutions and due to their polynomial time algorithms require reasonable computational effort, especially for solving large problem sizes. We consider three popular heuristics, multifit, combine and listfit since the seminal work of McNaughton in 1959. We present different experimental frameworks to investigate these heuristics for a comprehensive comparative performance evaluation. We show, through computational experimentation, that listfit outperforms the multifit and combine heuristics in most of the problem instances, however, at the cost of increased time complexity. The computational results also reveal that the combine heuristic performs better than the multifit heuristic, while requiring almost similar computational effort.

• Periodical: Advanced Materials Research (Volumes 488-489)
• Pages: 1708-1712
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.488-489.1708
• Online since: March 2012
• Authors: Dhiren Kumar Behera, Dipak Laha
• Keywords: Heuristics, Make Span, Optimization, Parallel Machine, Scheduling, Time Complexity

References

[1] R. McNaughton: Management Science Vo. 6 (1959), p.1.

[2] E. Mokotoff, J. L. Jimeno, and A. I. Gutierrez: TOP Vol. 9 (2001), p.243.

[3] L. H. Su and C. Y. Lien, Int. J. Production Economics Vol. 17 (2009), p.256.

[4] E. Mokotoff: Asia-Pacific Journal of Operational Research Vol. 18 (2001), p.193.

[5] T. C. E. Chen and C. C. S. Sin: European Journal of Operational Research Vol. 47 (1990), p.271.

[6] M. R. Garey and J. S. Johnson: Computers and intractability: A guide to the theory of NP-Completeness, (San Francisco CA, Freeman 1979).

[7] R. L. Graham: SIAM Journal of Applied Mathematics Vol. 17 (1969), p.416.

[8] E. G. Coffman, M. R. Garey and D. S. Johnson: SIAM Journal of Computing Vol. 7 (1978), p.1.

[9] C. Y. Lee and J. D. Massey: Discrete Applied Mathematics Vol. 20 (1988), p.233.

[10] J. N. D. Gupta and J. Ruiz-Torres: Production Planning & Control Vol. 12 (2001), p.28.

[11] G. Paletta and P. Pietramala: SIAM Journal of Discrete Math Vol. 21 (2007), p.313.

[12] M. Haouari, A. Gharbi and M. Jemmali: Intl. Trans. Op. Res. Vol. 13 (2006), p.529.

[13] M. Dell'Amico and S. Martello: ORSA Journal on Computing Vol. 7, (1995), p.191.

[14] S. M. T. Fatemi Ghomi and F. Jolai Ghazvini: Production Planning & Control Vol. 9 (1998), p.685.

[15] J. F. Lin and S. J. Chen: Computers Math. Applic Vol. 28 (1994), p.85.

[16] G. Chiaselotti, M. I. Gualtieri and P. Pietramala: J Math Model Algor Vol. 9 (2010), p.39.

[17] J. M. Van Den Akker, J. A. Hoogeveen and S. L. Van De Velde: Operations Research Vol. 47 (1999), p.862.

DOI: 10.1287/opre.47.6.862

[18] A. Dogramaci and J. Surkis: Management Science Vol. 25 (1979), p.1208.

[19] J. Chen , Q. K. Pan, L. Wang and J. Q. Li, Engineering Optimization (2011), p.1.

[20] A. H. Kashan and B. Karimi, Computers & Industrial Engineering Vol. 56 (2009), p.216.

[21] L. Min and W. Cheng: Artificial Intelligence in Engineering Vol. 13 (1999), p.399.

[22] W. C. Lee, C. C. Wu and P. Chen: Int J Adv Manuf Technol Vol. 31 (2006), p.328.

[23] M. Pinedo: Scheduling: Theory, algorithms, and systems (Prentice Hall, Upper Saddle River, New Jersey, 2002).

[24] D. K. Friesen: SIAM Journal of Computing Vol. 13 (1984), p.170.

[25] M. Yue: Annals of Operations Research Vol. 24 (1990), p.233.