×

An empirical analysis of the optimality rate of flow shop heuristics. (English) Zbl 1163.90815

Summary: If a certain optimization problem is NP-hard or even harder, one could expect that the chances of solving it optimally should rather decrease with an increase of the problem size. We reveal, however, that the opposite occurs for a strongly NP-hard problem, which requires sequencing \(n\) jobs through an \(m\) machine flow shop so as to minimize the makespan. In particular, we empirically examine optimality rates (the probability of being optimal) of the famous NEH heuristic of Nawaz et al. [Nawaz, M., Enscore, Jr., E., Ham, I., 1983. A heuristic algorithm for the \(m\)-machine, \(n\)-job flow-shop sequencing problem. Omega, The International Journal of Management Science 11, 91-95] and two improved versions of NEH. By using millions of simulation trials and a new effective lower bound on the shortest makespan, we observe relatively high optimality rates of the three heuristics for small values of \(m\). Rather surprisingly, for larger values of \(n\), the heuristics become more frequently optimal as \(n\) increases. Neither theoretical nor empirical studies of optimality rates of flow shop heuristics have been conducted so far, and - to the best of our knowledge - no similar studies are known in the field of operations research.

MSC:

90C59 Approximation methods and heuristics in mathematical programming

Software:

RANLUX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarval, A.; Colak, S.; Eryarsoy, E., Improvement heuristic for the flow-shop scheduling problem: An adaptive-learning approach, European Journal of Operational Research, 169, 801-815 (2006) · Zbl 1079.90044
[2] Aldowaisan, T.; Allahverdi, A., New heuristics for no-wait flowshops to minimize makespan, Computers & Operations Research, 30, 1219-1231 (2003) · Zbl 1047.90053
[3] Campbell, H. G.; Dudek, R. A.; Smith, M. L., A heuristic algorithm for the \(n\) job \(m\) machine sequencing problem, Management Science, 16, 630-637 (1970) · Zbl 0194.50504
[4] Chakraborty, U. K.; Laha, D., An improved heuristic for permutation flowshop scheduling, International Journal of Information and Communication Technology, 1, 89-97 (2007)
[5] Chen, B.; Potts, N.; Woeginger, G. J., A review of machine scheduling: Complexity, algorithms and approximability, (Du, D.-Z.; Pardalos, P. M., Handbook of Combinatorial Optimization (1998), Kluwer Academic Publishers.: Kluwer Academic Publishers. Dordrecht, The Netherlands), 21-170 · Zbl 0944.90022
[6] Companys, R.; Mateo, M., Different behaviour of a double branch-and-bound-algorithm on Fmprmu∣\(C_{max}\) and Fm∣block∣\(C_{max}\) problems, Computers & Operations Research, 34, 938-953 (2007) · Zbl 1107.90016
[7] Dannenbring, D. G., An evaluation of flow-shop sequencing heuristics, Management Science, 23, 1174-1182 (1977) · Zbl 0371.90063
[8] Dong, X.; Huang, H.; Chen, P., An improved NEH-based heuristic for the permutation flowshop problem, Computers and Operations Research, 35, 3962-3968 (2008) · Zbl 1278.90150
[9] Ekşioğlu, B.; Ekşioğlu, S. D.; Jain, P., A tabu search algorithm for the flowshop scheduling problem with changing neighbourhoods, Computers and Industrial Engineering, 54, 1-11 (2008)
[10] Etiler, O.; Toklu, B.; Atak, M.; Wilson, J., A genetic algorithm for flow shop scheduling problem, Journal of the Operational Research Society, 55, 830-835 (2004) · Zbl 1060.90035
[11] Framinan, J. M.; Leisten, R.; Rajendran, C., Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idle time or flowtime in the static permutation flowshop problem, International Journal of Production Research, 41, 121-148 (2003) · Zbl 1038.90027
[12] Framinan, J. M.; Gupta, J. N.D.; Leisten, R., A review and classification of heuristics for permutation flow-shop scheduling with makespan objective, Journal of the Operational Research Society, 55, 1243-1255 (2004), (Erratum (2005), 56, 351) · Zbl 1088.90022
[13] Gao, S.-W.; Lin, C.; Zhang, W.-D., Enhanced NEH method in solving permutation flow shop problem, Journal of Shanghai Jiaotong University (Science), 12, 47-52 (2007)
[14] Garey, M. R.D.; Johnson, D. S.; Sethi, R., The complexity of flow shop and job shop scheduling, Mathematics of Operations Research, 1, 117-129 (1976) · Zbl 0396.90041
[15] Gilmore, P. C.; Gomory, R. E., Sequencing a one state variable machine: A solvable case of the traveling salesman problem, Operations Research, 12, 655-679 (1964) · Zbl 0126.36006
[16] Glynn, P. W.; Whitt, W., Departures from many queues in series, Annals of Applied Probability, 1, 546-572 (1991) · Zbl 0749.60090
[17] Grabowski, J.; Pempera, J., Some local search algorithms for no-wait flow-shop problem with makespan criterion, Computers & Operations Research, 32, 2197-2212 (2005) · Zbl 1068.90058
[18] Grabowski, J.; Pempera, J., The permutation flowshop problem with blocking. A tabu search approach, Omega, the International Journal of Management Science, 35, 302-311 (2007)
[19] Grabowski, J.; Wodecki, M., A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion, Computers & Operations Research, 31, 1891-1909 (2004) · Zbl 1068.68143
[20] Gupta, J. N.D.; Koulamas, C.; Kyparisis, G. J., Performance guarantees for flowshop heuristics to minimize makespan, European Journal of Operational Research, 169, 865-872 (2006) · Zbl 1079.90052
[21] Hall, L., Approximability of flow shop scheduling, Mathematical Programming, 82, 175-190 (1998) · Zbl 0920.90073
[22] Haq, A. N.; Saravanan, M.; Vivekraj, A. R.; Prasad, T., A scatter search approach for general flow shop scheduling problem, International Journal of Advanced Manufacturing Technology, 31, 751-761 (2007)
[23] Iyer, S. K.; Saxena, B., Improved genetic algorithm for the permutation flowshop scheduling problem, Computers and Operations Research, 31, 593-606 (2004) · Zbl 1046.90028
[24] James, F., RANLUX: A Fortran implementation of the high-quality pseudorandom number generator of Luscher, Computer Physics Communications, 97, 357 (1996)
[25] Jarboui, B.; Ibrahim, S.; Siarry, P.; Rebai, A., A combinatorial particle swarm optimisation for solving permutation flowshop problems, Computers & Industrial Engineering, 54, 526-538 (2008)
[26] Jin, F.; Song, S.; Wu, C., An improved version of the NEH algorithm and its application to large-scale flow-shop scheduling problems, IIE Transactions, 39, 229-234 (2007)
[27] Johnson, S. M., Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, 61-68 (1954) · Zbl 1349.90359
[28] Johnson, S. M., Discussion: Sequencing \(n\) jobs on two machines with arbitrary time lags, Management Science, 5, 299-303 (1959) · Zbl 0995.90537
[29] Kalczynski, P. J.; Kamburowski, J., On the NEH heuristic for minimizing the makespan in permutation flowshops, Omega, The International Journal of Management Science, 35, 53-60 (2007)
[30] Kalczynski, P. J.; Kamburowski, J., An improved NEH heuristic to minimize makespan in permutation flow shops, Computers & Operations Research, 35, 3001-3008 (2008) · Zbl 1144.90499
[31] Koryakin, R., On asymptotic optimality of permutation schedules in stochastic flow shops and assembly lines, Operations Research Proceedings, Part 6, 200-206 (2004)
[32] Ladhari, T.; Haouari, M., A computational study of the permutation flow shop problem based on a tight lower bound, Computers & Operations Research, 32, 1831-1847 (2005) · Zbl 1074.90018
[33] Laha, D.; Mandal, P., Improved heuristically guided genetic algorithm for the flow shop scheduling problem, International Journal of Services and Operations Management, 3, 313-331 (2007)
[34] Lenstra, J. K.; Rinnoy Kan, A. H.G.; Brucker, P., Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, 343-362 (1977)
[35] Liao, C.-J.; Tseng, C.-T.; Luarn, P., A discrete version of particle swarm optimization for flowshop scheduling problems, Computers & Operations Research, 34, 3099-3111 (2007) · Zbl 1185.90083
[36] Liu, B.; Wang, L.; Jin, Y.-H., An effective hybrid particle swarm optimization for no-wait flow shop scheduling, International Journal of Advanced Manufacturing Technology, 31, 1001-1011 (2007)
[37] Liu, B.; Wang, L.; Jin, Y.-H., An effective PSO-based memetic algorithm for flow shop scheduling, IEEE Transactions on Systems, Man and Cybernetics - Part B. Cybernetics, 37, 18-27 (2007)
[38] Lourenço, H. L., Sevast’janov’s algorithm for the flow-shop scheduling problem, European Journal of Operational Research, 91, 176-189 (1996) · Zbl 0947.90591
[39] McMahon, G. B., A Study of Algorithms for Industrial Engineering Problems (1971), University of New South Wales: University of New South Wales Kensington
[40] Nawaz, M.; Enscore, E.; Ham, I., A heuristic algorithm for the \(m\)-machine, \(n\)-job flow-shop sequencing problem, Omega, The International Journal of Management Science, 11, 91-95 (1983)
[41] Nowicki, E., The permutation flow shop with buffers: A tabu search approach, European Journal of Operational Research, 116, 205-219 (1999) · Zbl 1009.90039
[42] Nowicki, E.; Smutnicki, C., New results in the worst-case analysis for flow-shop scheduling, Discrete Applied Mathematics, 46, 21-41 (1993) · Zbl 0848.68009
[43] Nowicki, E.; Smutnicki, C., A note on worst-case analysis of approximation algorithms for a scheduling problem, European Journal of Operational Research, 74, 128-134 (1994) · Zbl 0804.90073
[44] Nowicki, E.; Smutnicki, C., Some aspects of scatter search in the flow-shop problem, European Journal of Operational Research, 169, 654-666 (2006) · Zbl 1079.90058
[45] Onwubolu, G.; Davendra, D., Scheduling flow shops using differential evolution algorithm, European Journal of Operational Research, 171, 674-692 (2006) · Zbl 1090.90090
[46] Pan, Q.-K, Tasgetiren, M.F., Liang, Y.-C., 2007. A discrete differential evolution algorithm for the permutation flowshop scheduling problem. In: Ninth Annual Conference o Genetic and Evolutionary Computation, GECCO ‘07. London, UK.; Pan, Q.-K, Tasgetiren, M.F., Liang, Y.-C., 2007. A discrete differential evolution algorithm for the permutation flowshop scheduling problem. In: Ninth Annual Conference o Genetic and Evolutionary Computation, GECCO ‘07. London, UK.
[47] Pinedo, M., Scheduling: Theory, Algorithms, and Systems (2002), Prentice Hall: Prentice Hall Upper Saddle, NJ · Zbl 1145.90394
[48] Portougal, V. M., Asymptotic behaviour of some scheduling algorithms, Asia-Pacific Journal of Operational Research, 10, 79-91 (1993) · Zbl 0792.90038
[49] Portougal, V.; Smith, J. L., The asymptotic convergence of some flow-shop scheduling heuristics, Asia-Pacific Journal of Operational Research, 18, 243-256 (2001) · Zbl 1042.90565
[50] Prabhaharan, G.; Khan, B. S.H.; Rakesh, L., Implementation of grasp in flow shop scheduling, International Journal of Advanced Manufacturing Technology, 30, 1126-1131 (2006)
[51] Psaraftis, H. N., On the practical importance of asymptotic optimality in certain heuristic algorithms, Networks, 14, 587-596 (1984)
[52] Rad, S. F.; Ruiz, R.; Boroojerdian, N., New high performing heuristics for minimizing makespan in permutation flowshops, Omega, The International Journal of Operational Research, 37, 331-345 (2009)
[53] Rajendran, C.; Ziegler, H., Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs, European Journal of Operational Research, 155, 426-438 (2004) · Zbl 1045.90032
[54] Ramudhin, A.; Bratholdi, J. J.; Calvin, J.; Vande Vate, J. H.; Weiss, G., A probabilistic analysis of two-machine flowshops, Operations Research, 44, 899-908 (1996) · Zbl 0879.90117
[55] Reza Hejazi, S.; Saghafian, S., Flowshop-scheduling with makespan criterion: a review, International Journal of Production Research, 43, 2895-2929 (2005) · Zbl 1068.90059
[56] Ruiz, R.; Maroto, C., A comprehensive review and evaluation of permutation flowshop heuristics, European Journal of Operational Research, 165, 479-494 (2005) · Zbl 1066.90038
[57] Ruiz, R.; Stützle, T., A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, European Journal of Operational Research, 177, 2033-2049 (2007) · Zbl 1110.90042
[58] Ruiz, R.; Maroto, C.; Alcaraz, J., Two new robust genetic algorithms for the flowshop scheduling problem, Omega, The International Journal of Management Science, 34, 461-476 (2006)
[59] Schuurman, P., Woeginger, G.J., 2007. Approximation schemes – a tutorial. In: Moehring, R.H., Potts, C.N., Schulz, A.S., Woeginger, G.J., Wolsey, L.A. (Eds), Lectures on Scheduling. (available online).; Schuurman, P., Woeginger, G.J., 2007. Approximation schemes – a tutorial. In: Moehring, R.H., Potts, C.N., Schulz, A.S., Woeginger, G.J., Wolsey, L.A. (Eds), Lectures on Scheduling. (available online).
[60] Sevast’janov, S., Vector summation in Banach space and polynomial algorithms for flow shops and open shops, Mathematics of Operations Research, 20, 90-103 (1995) · Zbl 0834.90074
[61] Shmoys, D. B.; Stein, C.; Wein, J., Improved approximation algorithms for shop scheduling problems, SIAM Journal on Computing, 23, 617-632 (1994) · Zbl 0814.68026
[62] Smutnicki, C., Some results of the worst-case analysis for flow shop scheduling, European Journal of Operational Research, 109, 66-87 (1998) · Zbl 0987.90043
[63] Suliman, S. M.A., A two-phase heuristic approach to the permutation flow-shop scheduling problem, International Journal of Production Economics, 64, 143-152 (2000)
[64] Sviridenko, M. I., A note on the permutation flow shop problem, Annals of Operations Research, 129, 247-252 (2004) · Zbl 1056.90123
[65] Taillard, E., Some efficient heuristic methods for the flow shop sequencing problem, European Journal of Operational Research, 47, 65-74 (1990) · Zbl 0702.90043
[66] Taillard, E., Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 278-285 (1993) · Zbl 0769.90052
[67] Tasgetiren, M. Y-C. L.; Sevkli, M.; Gencyilmaz, G., A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem, European Journal of Operational Research, 177, 1930-1947 (2007) · Zbl 1110.90044
[68] Ying, K.-C.; Liao, C.-J., An ant colony system for permutation flow-shop sequencing, Computers & Operations Research, 31, 791-801 (2004) · Zbl 1048.90113
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.