An effective new heuristic algorithm for solving permutation flow shop scheduling problem

Document Type : Research Paper

Author

Department of Mathematics, Payame Noor University of ABCD, P.O.Box 19395-3697, Tehran, Iran

Abstract

The deterministic permutation flow shop scheduling problem with makespan criterion is not solvable in polynomial time‎. ‎Therefore‎, ‎researchers have thought about heuristic algorithms‎. ‎There are many heuristic algorithms for solving it that is a very important combinatorial optimization problem‎. ‎In this paper‎, ‎a new algorithm is proposed for solving the mentioned problem‎. ‎The presented algorithm chooses the weighted path that starts from the up-left corner and reaches the down-right in the matrix of jobs processing times and calculates the biggest sum of the times in the footprints of this path‎. ‎The row with the biggest sum permutes among all the rows of the matrix for locating the minimum of makespan‎. ‎This method was run on Taillard’s standard benchmark and the solutions were compared with the optimum or the best ones as well as 14 famous heuristics‎. ‎The validity and effectiveness of the algorithm are shown with tables and statistical evaluation‎.

Keywords

Main Subjects


[1] M. Ancău, On Solving Flowshop Scheduling Problems, Proc. Rom. Acad. Ser. A Math. Phys. Tech. Sci. Inf. Sci.,
13 (2012) 71–79.
[2] R. E. Bellman, A. O. Esogbue and I. Nabeshima, Mathematical aspects of scheduling and applications, International
Series in Modern Applied Mathematics and Computer Science, 4 (2014)
[3] M. C. Bonney and S. W. Gundry, Solutions to the constrained flowshop sequencing problem, Journal of the Opera-
tional Research Society, 27 (1976) 869–883.
[4] A. Brum and M. Ritt, Automatic Design of Heuristics for Minimizing the Makespan in Permutation Flow Shops,
In 2018 IEEE Congress on Evolutionary Computation (CEC), (2018) 1–8. IEEE.
[5] H. G. Campbell, R. A. Dudek and M. L. Smith, A heuristic algorithm for the n job, m machine sequencing problem,
Management Sci., 16 (1970) B–630.
[6] D. G. Dannenbring, An evaluation of flow shop sequencing heuristics, Management Sci., 23 (1977) 1174–1182.
[7] V. Fernandez-Viagas and J. M. Framinan, NEH-based heuristics for the permutation flowshop scheduling problem
to minimise total tardiness, Comput. Oper. Res., 60 (2015) 27–36.
[8] V. Fernandez-Viagas, J. M. Molina-Pariente and J. M. Framinan, Generalised accelerations for insertion-based
heuristics in permutation flowshop scheduling, European J. Oper. Res., 282 (2020) 858–872.
[9] V. Fernandez-Viagas, R. Ruiz and J. M. Framinan, A new vision of approximate methods for the permutation
flowshop to minimise makespan: State-of-the-art and computational evaluation, European J. Oper. Res., 257 (2017)
707–721.
[10] J. M. Framinan, J. N. Gupta and R. Leisten, A review and classification of heuristics for permutation flow-shop
scheduling with makespan objective, Journal of the Operational Research Society, 55 (2004) 1243–1255.
[11] M. R. Garey, D. S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling, Math. Oper. Res., 1
(1976) 117–129.
[12] R. L. Graham, E. L. Lawler, J. K. Lenstra and A. R. Kan, Optimization and approximation in deterministic
sequencing and scheduling: a survey, Ann. Discrete Math., 5 (1979) 287–326.
[13] J. N. Gupta, A functional heuristic algorithm for the flowshop scheduling problem, Journal of the Operational
Research Society, 22 (1971) 39–47.
[14] S. Hejazi and S. Saghafian, Flowshop-scheduling problems with makespan criterion: a review, International Journal
of Production Research, 43 (14) (2005) 2895–2929.
[15] J. C. Ho and Y. L. Chang, A new heuristic for the n-job, M-machine flow-shop problem, European J. Oper. Res.,
52 (1991) 194–202.
[16] T. S. Hundal and J. Rajgopal, An extension of Palmer’s heuristic for the flow shop scheduling problem, International
Journal Of Production Research, 26 (1988) 1119–1124.
[17] F. Jin, S. Song and C. Wu, An improved version of the NEH algorithm and its application to large-scale flow-shop
scheduling problems, IIE Trans., 39 (2007) 229–234.
[18] Johnson, S. M. Optimal twoand threestage production schedules with setup times included, Naval Res. Logist.
Quart., 1 (1954) 61-68.
[19] Kalczynski, P. J., & Kamburowski, J. On the NEH heuristic for minimizing the makespan in permutation flow
shops, Omega, 35 (2007) 53-60.
[20] King, J. R., & Spachis, A. S. Heuristics for flow-shop scheduling, International Journal of Production Research, 18
(1980) 345-357.
[21] Koulamas, C. A new constructive heuristic for the flowshop scheduling problem, European J. Oper. Res., 105 (1998)
66-71.
[22] Liu, W., Jin, Y., & Price, M. A new NawazEnscoreHam-based heuristic for permutation flow-shop problems with
bicriteria of makespan and machine idle time, Eng. Optim., 48 (2016) 1808-1822.
[23] Malik, A., & Dhingra, A. K. Comparative analysis of heuristics for make span minimizing in flow shop scheduling,
International Journal of Innovations in Engineering and Technology, 2 (2013) 263-269.
[24] Nawaz, M., Enscore, Jr, E. E., & Ham, I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing
problem, Omega, 11 (1983) 91-95.
[25] Nurdiansyah, R., Rijanto, O. A. W., Santosa, B., & Wiratno, S. E. An Improved Differential Evolution Algorithm
for Permutation Flow Shop Scheduling Problem, Int. J. Oper. Res. (Taichung), 16 (2019) 37-44.
[26] Page, E. S. An approach to the scheduling of jobs on machines, J. Roy. Statist. Soc. Ser. B (Methodological), 23
(1961) 484-492.
[27] Palmer, D. S. Sequencing jobs through a multi-stage process in the minimum total time–a quick method of obtaining a near optimum, Journal of the Operational Research Society, 16 (1965) 101-107.
[28] Potts, C. N., & Strusevich, V. A. Fifty years of scheduling: a survey of milestones, Journal of the Operational
Research Society, 60 (2009) S41-S68.
[29] Rad, S. F., Ruiz, R., & Boroojerdian, N. New high performing heuristics for minimizing makespan in permutation
flowshops, Omega, 37 (2009) 331-345.
[30] Ruiz, R., & Maroto, C. A comprehensive review and evaluation of permutation flowshop heuristics, European J.
Oper. Res., 165 (2005) 479-494.
[31] Sarin, S., & Lefoka, M. Scheduling heuristic for the n-jobm-machine flow shop, Omega, 21 (1993) 229-234.
[32] Sauvey, C., & Sauer, N. Two NEH Heuristic Improvements for Flowshop Scheduling Problem with Makespan
Criterion, Algorithms, 13 (2020) 112.
[33] Singhal, E., Singh, S., & Dayma, A. An Improved Heuristic for Permutation Flow Shop Scheduling, In (NEH
ALGORITHM). International Journal of Computational Engineering Research, 2 (2012) 95-100.
[34] STINSON, J. P., & SMITH, A. W. A heuristic prorammin procedure for sequencin the static flowshop, The Inter-
national Journalof Production Research, 20 (1982) 753-764.
[35] Suliman, S. M. A. A two-phase heuristic approach to the permutation flow-shop scheduling problem, International
Journal of Production Economics, 64 (2000) 143-152.
[36] Taillard, E. Benchmarks for basic scheduling problems, European J. Oper. Res., 64 (1993) 278-285.
[37] Taillard, E. Some efficient heuristic methods for the flow shop sequencing problem, European J. Oper. Res., 47
(1990) 65-74.
[38] T’kindt, V., & Billaut, J. C. Multicriteria scheduling: theory, models and algorithms, Springer Science & Business
Media, (2006).
[39] E. Vallada, R. Ruiz and J. M. Framinan, New hard benchmark for flowshop scheduling problems minimising
makespan, European J. Oper. Res., 240 (2015) 666-677.
[40] J. Xu, Y. Yin, T. C. E. Cheng, C. C. Wu and S. Gu, An improved memetic algorithm based on a dynamic
neighbourhood for the permutation flowshop scheduling problem, Int. J. Prod. Res., 52 (2014) 1188–1199.
Volume 11, Issue 1
March 2022
Pages 15-27
  • Receive Date: 10 December 2020
  • Revise Date: 23 January 2021
  • Accept Date: 30 January 2021
  • Published Online: 01 March 2022