A new vision of approximate methods for the permutation flowshop to minimise makespan: state-of-the-art and computational evaluation. (English) Zbl 1394.90271
Summary: The permutation flowshop problem is a classic machine scheduling problem where \(n\) jobs must be processed on a set of \(m\) machines disposed in series and where each job must visit all machines in the same order. Many production scheduling problems resemble flowshops and hence it has generated much interest and had a big impact in the field, resulting in literally hundreds of heuristic and metaheuristic methods over the last 60 years. However, most methods proposed for makespan minimisation are not properly compared with existing procedures so currently it is not possible to know which are the most efficient methods for the problem regarding the quality of the solutions obtained and the computational effort required. In this paper, we identify and exhaustively compare the best existing heuristics and metaheuristics so the state-of-the-art regarding approximate procedures for this relevant problem is established.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C35 | Programming involving graphs or networks |
References:
| [1] | Agarwal, A.; Colak, S.; Eryarsoy, E., Improvement heuristic for the flow-shop scheduling problem: An adaptive-learning approach, European Journal of Operational Research, 169, 3, 801-815 (2006) · Zbl 1079.90044 |
| [2] | Ahmadizar, F., A new ant colony algorithm for makespan minimization in permutation flow shops, Computers and Industrial Engineering, 63, 2, 355-361 (2012) |
| [3] | Carlier, J., Ordonnancements a contraintes disjonctives, RAIRO Recherche Operationnelle, 12, 4, 333-350 (1978) · Zbl 0401.90052 |
| [4] | Chang, P.-C.; Chen, M.-H., A block based estimation of distribution algorithm using bivariate model for scheduling problems, Soft Computing, 18, 6, 1177-1188 (2014) |
| [5] | Chang, P.-C.; Chen, M.-H.; Tiwari, M.; Iquebal, A., A block-based evolutionary algorithm for flow-shop scheduling problem, Applied Soft Computing Journal, 13, 12, 4536-4547 (2013) |
| [6] | Chang, P.-C.; Chen, S.-H.; Fan, C.-Y.; Chan, C.-L., Genetic algorithm integrated with artificial chromosomes for multi-objective flowshop scheduling problems, Applied Mathematics and Computation, 205, 2, 550-561 (2008) · Zbl 1152.90432 |
| [7] | Chang, P.-C.; Chen, S.-H.; Fan, C.-Y.; Mani, V., Generating artificial chromosomes with probability control in genetic algorithm for machine scheduling problems, Annals of Operations Research, 180, 1, 197-211 (2010) · Zbl 1202.90128 |
| [8] | Chang, P.-C.; Hsieh, J.-C.; Chen, S.-H.; Lin, J.-L.; Huang, W.-H., Artificial chromosomes embedded in genetic algorithm for a chip resistor scheduling problem in minimizing the makespan, Expert Systems with Applications, 36, 3 PART 2, 7135-7141 (2009) |
| [9] | Chang, P.-C.; Huang, W.-H.; Ting, C.-J., A hybrid genetic-immune algorithm with improved lifespan and elite antigen for flow-shop scheduling problems, International Journal of Production Research, 49, 17, 5207-5230 (2011) · Zbl 1356.90053 |
| [10] | Chen, C.-L.; Tzeng, Y.-R.; Chen, C.-L., A new heuristic based on local best solution for permutation flow shop scheduling, Applied Soft Computing Journal, 29, 75-81 (2015) |
| [11] | Chen, R.-M.; Hsieh, F.-R., An exchange local search heuristic based scheme for permutation flow shop problems, Applied Mathematics and Information Sciences, 8, 1 L, 209-215 (2014) |
| [12] | Chen, S.-H.; Chang, P.-C.; Cheng, T.; Zhang, Q., A self-guided genetic algorithm for permutation flowshop scheduling problems, Computers and Operations Research, 39, 7, 1450-1457 (2012) · Zbl 1251.90122 |
| [13] | Dasgupta, P.; Das, S., A discrete inter-species cuckoo search for flowshop scheduling problems, Computers and Operations Research, 60, 0, 111-120 (2015) · Zbl 1348.90248 |
| [14] | Demirkol, E.; Mehta, S.; Uzsoy, R., Benchmarks for shop scheduling problems, European Journal of Operational Research, 109, 1, 137-141 (1998) · Zbl 0951.90022 |
| [15] | Dong, X.; Huang, H.; Chen, P., An improved NEH-based heuristic for the permutation flowshop problem, Computers and Operations Research, 35, 12, 3962-3968 (2008) · Zbl 1278.90150 |
| [16] | Eksioglu, B.; Eksioglu, S.; Jain, P., A tabu search algorithm for the flowshop scheduling problem with changing neighborhoods, Computers and Industrial Engineering, 54, 1, 1-11 (2008) |
| [17] | Etiler, O.; Toklu, B.; Atak, M.; Wilson, J., A genetic algorithm for flow shop scheduling problems, Journal of the Operational Research Society, 55, 8, 830-835 (2004) · Zbl 1060.90035 |
| [18] | Fernandez-Viagas, V.; Framinan, J., A new set of high-performing heuristics to minimise flowtime in permutation flowshops, Computers and Operations Research, 53, 68-80 (2015) · Zbl 1348.90257 |
| [19] | Fernandez-Viagas, V.; Framinan, J., NEH-based heuristics for the permutation flowshop scheduling problem to minimise total tardiness, Computers and Operations Research, 60, 27-36 (2015) · Zbl 1348.90258 |
| [20] | Fernandez-Viagas, V.; Framinan, J. M., On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem, Computers and Operations Research, 45, 60-67 (2014) · Zbl 1348.90256 |
| [21] | Framinan, J.; Gupta, J.; Leisten, R., A review and classification of heuristics for permutation flow-shop scheduling with makespan objective, Journal of the Operational Research Society, 55, 12, 1243-1255 (2004) · Zbl 1088.90022 |
| [22] | Framinan, J.; Leisten, R., A heuristic for scheduling a permutation flowshop with makespan objective subject to maximum tardiness, International Journal of Production Economics, 99, 1-2, 28-40 (2006) |
| [23] | Framinan, J.; Pastor, R., A proposal for a hybrid meta-strategy for combinatorial optimization problems, Journal of Heuristics, 14, 4, 375-390 (2008) · Zbl 1151.90524 |
| [24] | Haq, A.; Ramanan, T.; Shashikant, K.; Sridharan, R., A hybrid neural network-genetic algorithm approach for permutation flow shop scheduling, International Journal of Production Research, 48, 14, 4217-4231 (2010) · Zbl 1197.90205 |
| [25] | Hariharan, R.; Golden Renjith Nimal, R., Solving flow shop scheduling problems using a hybrid genetic scatter search algorithm, Middle - East Journal of Scientific Research, 20, 3, 328-333 (2014) |
| [26] | Heller, J., Some numerical experiments for an m x j flow shop and its decision-theoretical aspects, Operations Research, 8, 2, 178-184 (1960) · Zbl 0092.27910 |
| [27] | Hsu, C.-Y.; Chang, P.-C.; Chen, M.-H., A linkage mining in block-based evolutionary algorithm for permutation flowshop scheduling problem, Computers and Industrial Engineering, 83, 159-171 (2015) |
| [28] | Huang, W.; Wang, L., A local search method for permutation flow shop scheduling, Journal of the Operational Research Society, 57, 10, 1248-1251 (2006) · Zbl 1123.90080 |
| [29] | Jarboui, B.; Ibrahim, S.; Siarry, P.; Rebai, A., A combinatorial particle swarm optimisation for solving permutation flowshop problems, Computers and Industrial Engineering, 54, 3, 526-538 (2008) |
| [30] | Kalczynski, P. J.; Kamburowski, J., On the NEH heuristic for minimizing the makespan in permutation flow shops, OMEGA, The International Journal of Management Science, 35, 1, 53-60 (2007) |
| [31] | Kalczynski, P. J.; Kamburowski, J., An improved NEH heuristic to minimize makespan in permutation flow shops, Computers and Operations Research, 35, 9, 3001-3008 (2008) · Zbl 1144.90499 |
| [32] | Kalczynski, P. J.; Kamburowski, J., An empirical analysis of the optimality rate of flow shop heuristics, European Journal of Operational Research, 198, 1, 93-101 (2009) · Zbl 1163.90815 |
| [33] | Kendall, G.; Bai, R.; Błazewicz, J.; Causmaecker, P. D.; Gendreau, M.; John, R., Good laboratory practice for optimization research, Journal of the Operational Research Society, 67, 4, 676-689 (2016) |
| [34] | Kuo, I.-H.; Horng, S.-J.; Kao, T.-W.; Lin, T.-L.; Lee, C.-L.; Terano, T., An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model, Expert Systems with Applications, 36, 3 PART 2, 7027-7032 (2009) |
| [35] | Laha, D.; Chakraborty, U., An efficient hybrid heuristic for makespan minimization in permutation flow shop scheduling, International Journal of Advanced Manufacturing Technology, 44, 5-6, 559-569 (2009) |
| [36] | Leisten, R.; Rajendran, C., Variability of completion time differences in permutation flow shop scheduling, Computers and Operations Research, 54, 155-167 (2014) · Zbl 1348.90284 |
| [37] | Li, X.; Yin, M., A discrete artificial bee colony algorithm with composite mutation strategies for permutation flow shop scheduling problem, Scientia Iranica, 19, 6, 1921-1935 (2012) |
| [38] | Li, X.; Yin, M., A hybrid cuckoo search via Lévy flights for the permutation flow shop scheduling problem, International Journal of Production Research, 51, 16, 4732-4754 (2013) |
| [39] | Li, X.; Yin, M., An opposition-based differential evolution algorithm for permutation flow shop scheduling based on diversity measure, Advances in Engineering Software, 55, 10-31 (2013) |
| [40] | Lian, Z.; Gu, X.; Jiao, B., A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan, Applied Mathematics and Computation, 175, 1, 773-785 (2006) · Zbl 1137.90503 |
| [41] | Lian, Z.; Gu, X.; Jiao, B., A novel particle swarm optimization algorithm for permutation flow-shop scheduling to minimize makespan, Chaos, Solitons and Fractals, 35, 5, 851-861 (2008) · Zbl 1146.90418 |
| [42] | Liao, C.-J.; Tseng, C.-T.; Luarn, P., A discrete version of particle swarm optimization for flowshop scheduling problems, Computers and Operations Research, 34, 10, 3099-3111 (2007) · Zbl 1185.90083 |
| [43] | Lin, Q.; Gao, L.; Li, X.; Zhang, C., A hybrid backtracking search algorithm for permutation flow-shop scheduling problem, Computers and Industrial Engineering, 85, 437-446 (2015) |
| [44] | 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, 1, 18-27 (2007) |
| [45] | Liu, H.; Gao, L.; Pan, Q.-K., A hybrid particle swarm optimization with estimation of distribution algorithm for solving permutation flowshop scheduling problem, Expert Systems with Applications, 38, 4, 4348-4360 (2011) |
| [46] | Liu, R.; Ma, C.; Ma, W.; Li, Y., A multipopulation pso based memetic algorithm for permutation flow shop scheduling, The Scientific World Journal (2013) |
| [47] | Liu, Y.; Yin, M.; Gu, W., An effective differential evolution algorithm for permutation flow shop scheduling problem, Applied Mathematics and Computation, 248, 143-159 (2014) · Zbl 1338.90174 |
| [48] | Liu, Y.-F.; Liu, S.-Y., A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem, Applied Soft Computing Journal, 13, 3, 1459-1463 (2013) |
| [49] | Low, C.; Yeh, J.-Y.; Huang, K.-I., A robust simulated annealing heuristic for flow shop scheduling problems, International Journal of Advanced Manufacturing Technology, 23, 9-10, 762-767 (2004) |
| [50] | Marinakis, Y.; Marinaki, M., Particle swarm optimization with expanding neighborhood topology for the permutation flowshop scheduling problem, Soft Computing, 17, 7, 1159-1173 (2013) |
| [51] | M’Hallah, R., An iterated local search variable neighborhood descent hybrid heuristic for the total earliness tardiness permutation flow shop, International Journal of Production Research, 52, 13, 3802-3819 (2014) |
| [52] | Nagano, M.; Moccellin, J., A high quality solution constructive heuristic for flow shop sequencing, Journal of the Operational Research Society, 53, 12, 1374-1379 (2002) · Zbl 1139.90344 |
| [53] | Nagano, M.; Ruiz, R.; Lorena, L., A constructive genetic algorithm for permutation flowshop scheduling, Computers and Industrial Engineering, 55, 1, 195-207 (2008) |
| [54] | Nanz, S.; Furia, C. A., A comparative study of programming languages in rosetta code, Proceedings of the 37th international conference on software engineering, vol. 1, 778 (2015) |
| [55] | 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, 1, 91-95 (1983) |
| [56] | Nearchou, A., The effect of various operators on the genetic search for large scheduling problems, International Journal of Production Economics, 88, 2, 191-203 (2004) |
| [57] | Nearchou, A., Flow-shop sequencing using hybrid simulated annealing, Journal of Intelligent Manufacturing, 15, 3, 317-328 (2004) |
| [58] | Nearchou, A., A novel metaheuristic approach for the flow shop scheduling problem, Engineering Applications of Artificial Intelligence, 17, 3, 289-300 (2004) |
| [59] | Nowicki, E.; Smutnicki, C., A fast tabu search algorithm for the permutation flow-shop problem, European Journal of Operational Research, 91, 1, 160-175 (1996) · Zbl 0947.90590 |
| [60] | Nowicki, E.; Smutnicki, C., Some aspects of scatter search in the flow-shop problem, European Journal of Operational Research, 169, 2, 654-666 (2006) · Zbl 1079.90058 |
| [61] | Onwubolu, G.; Davendra, D., Scheduling flow shops using differential evolution algorithm, European Journal of Operational Research, 171, 2, 674-692 (2006) · Zbl 1090.90090 |
| [62] | Pan, Q.-K.; Tasgetiren, M.; Liang, Y.-C., A discrete differential evolution algorithm for the permutation flowshop scheduling problem, Computers and Industrial Engineering, 55, 4, 795-816 (2008) |
| [63] | Pinedo, M., Scheduling: Theory, algorithms and systems (2012), Prentice Hall · Zbl 1239.90002 |
| [64] | Prabhaharan, G.; Khan, B.; Rakesh, L., Implementation of GRASP in flow shop scheduling, International Journal of Advanced Manufacturing Technology, 30, 11-12, 1126-1131 (2006) |
| [65] | Qian, B.; Wang, L.; Hu, R.; Wang, W.-L.; Huang, D.-X.; Wang, X., A hybrid differential evolution method for permutation flow-shop scheduling, International Journal of Advanced Manufacturing Technology, 38, 7-8, 757-777 (2008) |
| [66] | Rad, S. F.; Ruiz, R.; Boroojerdian, N., New high performing heuristics for minimizing makespan in permutation flowshops, OMEGA, The International Journal of Management Science, 37, 2, 331-345 (2009) |
| [67] | Rajendran, C.; Ziegler, H., Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs, European Journal of Operational Research, 155, 2, 426-438 (2004) · Zbl 1045.90032 |
| [68] | Rajkumar, R.; Shahabudeen, P., An improved genetic algorithm for the flowshop scheduling problem, International Journal of Production Research, 47, 1, 233-249 (2009) · Zbl 1152.90462 |
| [69] | Ramanan, T.; Sridharan, R.; Shashikant, K.; Haq, A., An artificial neural network based heuristic for flow shop scheduling problems, Journal of Intelligent Manufacturing, 22, 2, 279-288 (2011) |
| [70] | Reeves, C., A genetic algorithm for flowshop sequencing, Computers and Operations Research, 22, 1, 5-13 (1995) · Zbl 0815.90097 |
| [71] | Reza Hejazi, S.; Saghafian, S., Flowshop-scheduling problems with makespan criterion: A review, International Journal of Production Research, 43, 14, 2895-2929 (2005) · Zbl 1068.90059 |
| [72] | Ribas, I.; Companys, R.; Tort-Martorell, X., Comparing three-step heuristics for the permutation flow shop problem, Computers and Operations Research, 37, 12, 2062-2070 (2010) |
| [73] | Rinnooy Kan, A. H.G., Machine scheduling problems: Classification, complexity and computations (1976), Martinus Nijhoff: Martinus Nijhoff The Hague |
| [74] | Ruiz, R.; Maroto, C., A comprehensive review and evaluation of permutation flowshop heuristics, European Journal of Operational Research, 165, 2, 479-494 (2005) · Zbl 1066.90038 |
| [75] | Ruiz, R.; Maroto, C.; Alcaraz, J., Two new robust genetic algorithms for the flowshop scheduling problem, OMEGA, The International Journal of Management Science, 34, 5, 461-476 (2006) |
| [76] | Ruiz, R.; Stützle, T., A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, European Journal of Operational Research, 177, 3, 2033-2049 (2007) · Zbl 1110.90042 |
| [77] | Saravanan, M.; Noorul Haq, A.; Vivekraj, A.; Prasad, T., Performance evaluation of the scatter search method for permutation flowshop sequencing problems, International Journal of Advanced Manufacturing Technology, 37, 11-12, 1200-1208 (2008) |
| [78] | Sayadi, M.; Ramezanian, R.; Ghaffari-Nasab, N., A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems, International Journal of Industrial Engineering Computations, 1, 1, 1-10 (2010) |
| [79] | Solimanpur, M.; Vrat, P.; Shankar, R., A neuro-tabu search heuristic for the flow shop scheduling problem, Computers and Operations Research, 31, 13, 2151-2164 (2004) · Zbl 1068.68040 |
| [80] | Stütze, T., Applying iterated local search to the permutation flow shop problem, Technical report, AIDA-98-04, FG Intellektik, FB Informatik, TU Darmstadt (1998) |
| [81] | Sun, Y.; Zhang, C.; Gao, L.; Wang, X., Multi-objective optimization algorithms for flow shop scheduling problem: A review and prospects, International Journal of Advanced Manufacturing Technology, 55, 5-8, 723-739 (2011) |
| [82] | Taillard, E., Some efficient heuristic methods for the flow shop sequencing problem, European Journal of Operational Research, 47, 1, 65-74 (1990) · Zbl 0702.90043 |
| [83] | Taillard, E., Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 2, 278-285 (1993) · Zbl 0769.90052 |
| [84] | Tasgetiren, M.; Liang, Y.-C.; 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, 3, 1930-1947 (2007) · Zbl 1110.90044 |
| [85] | Tseng, L.-Y.; Lin, Y.-T., A hybrid genetic local search algorithm for the permutation flowshop scheduling problem, European Journal of Operational Research, 198, 1, 84-92 (2009) · Zbl 1163.90532 |
| [86] | Tzeng, Y.-R.; Chen, C.-L., A hybrid eda with acs for solving permutation flow shop scheduling, International Journal of Advanced Manufacturing Technology, 60, 9-12, 1139-1147 (2012) |
| [87] | Vallada, E.; Ruiz, R., Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem, OMEGA, The International Journal of Management Science, 38, 1-2, 57-67 (2010) |
| [88] | Vallada, E.; Ruiz, R.; Framinan, J., New hard benchmark for flowshop scheduling problems minimising makespan, European Journal of Operational Research, 240, 666-677 (2015) · Zbl 1338.90185 |
| [89] | Vasiljevic, D.; Danilovic, M., Handling ties in heuristics for the permutation flow shop scheduling problem, Journal of Manufacturing Systems, 35, 1-9 (2015) |
| [90] | Watson, J.; Barbulescu, L.; Whitley, L.; Howe, A., Contrasting structured and random permutation flow-shop scheduling problems: Search-space topology and algorithm performance, INFORMS Journal on Computing, 14, 2, 98-123 (2002) · Zbl 1238.90072 |
| [91] | Xie, Z.; Zhang, C.; Shao, X.; Lin, W.; Zhu, H., An effective hybrid teaching-learning-based optimization algorithm for permutation flow shop scheduling problem, Advances in Engineering Software, 77, 35-47 (2014) |
| [92] | Yagmahan, B.; Yenisey, M., Ant colony optimization for multi-objective flow shop scheduling problem, Computers and Industrial Engineering, 54, 3, 411-420 (2008) |
| [93] | Ying, K.-C.; Liao, C.-J., An ant colony system for permutation flow-shop sequencing, Computers and Operations Research, 31, 5, 791-801 (2004) · Zbl 1048.90113 |
| [94] | Ying, K.-C.; Lin, S.-W., A high-performing constructive heuristic for minimizing makespan in permutation flowshops, Journal of Industrial and Production Engineering, 30, 6, 355-362 (2013) |
| [95] | Zanakis, S.; Evans, J.; Vazacopoulos, A., Heuristic methods and applications: A categorized survey, European Journal of Operational Research, 43, 1, 88-110 (1989) · Zbl 0681.90090 |
| [96] | Zhang, C.; Ning, J.; Ouyang, D., A hybrid alternate two phases particle swarm optimization algorithm for flow shop scheduling problem, Computers and Industrial Engineering, 58, 1, 1-11 (2010) |
| [97] | Zhang, C.; Sun, J., An alternate two phases particle swarm optimization algorithm for flow shop scheduling problem, Expert Systems with Applications, 36, 3 PART 1, 5162-5167 (2009) |
| [98] | Zhang, C.; Sun, J.; Zhu, X.; Yang, Q., An improved particle swarm optimization algorithm for flowshop scheduling problem, Information Processing Letters, 108, 4, 204-209 (2008) · Zbl 1191.68112 |
| [99] | Zhang, J.; Zhang, C.; Liang, S., The circular discrete particle swarm optimization algorithm for flow shop scheduling problem, Expert Systems with Applications, 37, 8, 5827-5834 (2010) · Zbl 1201.80060 |
| [100] | Zhang, L.; Wu, J., A PSO-based hybrid metaheuristic for permutation flowshop scheduling problems, The Scientific World Journal (2014) |
| [101] | Zheng, T.; Yamashiro, M., Solving flow shop scheduling problems by quantum differential evolutionary algorithm, International Journal of Advanced Manufacturing Technology, 49, 5-8, 643-662 (2010) |
| [102] | Zobolas, G.; Tarantilis, C.; Ioannou, G., Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm, Computers and Operations Research, 36, 4, 1249-1267 (2009) · Zbl 1160.90490 |
| [103] | Zäpfel, G.; Braune, R.; Bögl, M., Metaheuristic search concepts (2010), Springer |
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.
