×

Two simple and effective heuristics for minimizing the makespan in non-permutation flow shops. (English) Zbl 1349.90318

Summary: We propose a constructive and an iterated local search heuristic for minimizing the makespan in the non-permutation flow shop scheduling problem. Both heuristics are based on the observation that optimal non-permutation schedules often exhibit a permutation structure with a few local job inversions. In computational experiments we compare our heuristics to the best heuristics for finding non-permutation and permutation flow shop schedules, and evaluate the reduction in makespan and buffer size that can be achieved by non-permutation schedules.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brucker, P.; Heitmann, S.; Hurink, J., Flow-shop problems with intermediate buffers, OR Spectr, 25, 549-574 (2003) · Zbl 1042.90016
[2] Carlier, J., The one-machine sequencing problem, Eur J Oper Res, 11, 42-47 (1982) · Zbl 0482.90045
[3] Chen, B.; Glass, C. A.; Potts, C. N.; Strusevich, V. A., A new heuristic for three-machine flow shop scheduling, Oper Res, 44, 891-898 (1996) · Zbl 0879.90112
[4] Dannenbring, D. G., An evaluation of flow shop sequencing heuristics, Manag Sci, 23 (1977) · Zbl 0371.90063
[5] Demirkol, E.; Mehta, S.; Uzsoy, R., Benchmarks for shop scheduling problems, Eur J Oper Res, 109, 137-141 (1998) · Zbl 0951.90022
[6] Dong, X.; Huang, H.; Chen, P., An improved NEH-based heuristic for the permutation flowshop problem, Comput Oper Res, 35, 3962-3968 (2008) · Zbl 1278.90150
[7] Fernandez-Viagas, V.; Framinan, J. M., On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem, Comput Oper Res, 45, 60-67 (2014) · Zbl 1348.90256
[8] Glover, F., Tabu search for nonlinear and parametric optimisation (with links to genetic algorithms), Discrete Appl Math, 49, 231-255 (1994) · Zbl 0799.90109
[9] Gonzalez, T.; Sahni, S., Flowshop and jobshop schedulescomplexity and approximation, Oper Res, 26, 36-52 (1978) · Zbl 0371.90061
[10] Grabowski, J.; Wodecki, M., A very fast tabu search algorithm for the permutation flowshop problem with makespan criterion, Comput Oper Res, 31, 1891-1909 (2004) · Zbl 1068.68143
[11] Jain, A. S.; Meeran, S., A multi-level hyrbid framework applied to the general flow-shop scheduling problem, Comput Oper Res, 29, 1873-1901 (2002)
[12] Johnson, S. M., Optimal two- and three-stage production schedules with setup times included, Nav Res Logist, 1, 61-68 (1954) · Zbl 1349.90359
[13] Kalczynski, P. J.; Kamburowski, J., On the NEH heuristic for minimizing the makespan in permutation flow shops, Omega, 35, 53-60 (2007)
[14] Kalczynski, P. J.; Kamburowski, J., An improved NEH heuristic to minimize makespan in permutation flow shops, Comput Oper Res, 35, 3001-3008 (2008) · Zbl 1144.90499
[15] Kalczynski, P. J.; Kamburowski, J., An empirical analysis of the optimality rate of flow shop heuristics, Eur J Oper Res, 198, 93-101 (2009) · Zbl 1163.90815
[16] Kalczynski, P. J.; Kamburowski, J., On recent modifications and extensions of the NEH heuristic for flow shop sequencing, Found Comput Sci Decision Sci, 36, 17-33 (2011) · Zbl 1211.90087
[17] Koulamas, C., A new constructive heuristic for the flowshop scheduling problem, Eur J Oper Res, 105, 66-71 (1998) · Zbl 0957.90053
[18] Krone, M. J.; Steiglitz, K., Heuristic-programming solution of a flowshop-scheduling problem, Oper Res, 22, 629-638 (1974) · Zbl 0279.90021
[19] Leisten, R., Flowshop sequencing problems with limited buffer constraints, Int J Prod Res, 28, 2085-2100 (1990) · Zbl 0707.90054
[20] Liao, C. J.; Liao, L. M.; Tseng, C. T., A performance evaluation of permutation vs. non-permutation schedules in a flowshop, Int J Prod Res, 44, 4297-4309 (2006)
[21] Lin, S.-W.; Ying, K.-C., Applying a hybrid simulated annealing and tabu search approach to non-permutation flowshop scheduling problems, Int J Prod Res, 47, 1411-1424 (2009)
[22] Nagarajan, V.; Sviridenko, M., Tight bounds for permutation flow shop scheduling, Math Oper Res, 34, 417-427 (2009) · Zbl 1231.90209
[23] Nawaz, M.; Enscore, E.; Ham, I., A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega, 11, 91-95 (1983)
[24] Nowicki, E.; Smutnicki, C., A fast tabu search algorithm for the permutation flow-shop problem, Eur J Oper Res, 91, 160-175 (1996) · Zbl 0947.90590
[25] Osman, I.; Potts, C., Simulated annealing for permutation flow shop scheduling, Omega, 17, 551-557 (1989)
[26] Pan, Q.-K.; Tasgetiren, M. F.; Liang, Y.-C., A discrete differential evolution algorithm for the permutation flowshop scheduling problem, Comput Ind Eng, 55, 795-816 (2008)
[27] Potts, C. N.; Shmoys, D. B.; Williamson, D. P., Permutation vs. non-permutation flow shop schedules, Oper Res Lett, 10, 281-284 (1991) · Zbl 0742.90045
[28] Pugazhendhi, S.; Thiagarajan, S.; Rajendran, C.; Anantharaman, N., Performance enhancement by using non-permutation schedules in flowline-based manufacturing systems, Comput Ind Eng, 44, 133-157 (2002)
[29] Rajendran, C.; Ziegler, H., Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs, Eur J Oper Res, 155, 426-438 (2004) · Zbl 1045.90032
[30] Reeves, C. R., A genetic algorithm for flowshop sequencing, Comput Oper Res, 22, 5-13 (1995) · Zbl 0815.90097
[31] Rossi, A.; Lanzetta, M., Native metaheuristics for non-permutation flowshop scheduling, J. Intell. Manuf., 25, 1221-1233 (2014)
[32] Rossi, A.; Lanzetta, M., Scheduling flow lines with buffers by ant colony digraph, Exp Syst Appl, 40, 3328-3340 (2013)
[33] Ruiz, R.; Maroto, C.; Alcaraz, J., Two new robust genetic algorithms for the flowshop scheduling problem, Omega, 34, 461-476 (2006)
[34] Ruiz, R.; Maroto, C., A comprehensive review and evaluation of permutation flowshop heuristics, Eur J Oper Res, 165, 479-494 (2005) · Zbl 1066.90038
[35] Ruiz, R.; Stützle, T., A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, Eur J Oper Res, 177, 2033-2049 (2007) · Zbl 1110.90042
[36] Sadjadi, S. J.; Bouquard, J. L.; Ziaee, M., An ant colony algorithm for the flowshop scheduling problem, J Appl Sci, 8, 3938-3944 (2008)
[37] Taillard, E., Some efficient heuristic methods for the flow shop sequencing problem, Eur J Oper Res, 47, 65-74 (1990) · Zbl 0702.90043
[38] Taillard, E., Benchmarks for basic scheduling problems, Eur J Oper Res, 64, 278-285 (1993) · Zbl 0769.90052
[40] Tandon, M.; Cummings, P.; Levan, M., Flowshop sequencing with non-permutation schedules, Comput Chem Eng, 15, 601-607 (1991)
[41] Tasgetiren, M.; Liang, Y.; Sevkli, M.; Gencyilmaz, G., A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem, Eur J Oper Res, 177, 1930-1947 (2007) · Zbl 1110.90044
[42] Yagmahan, B.; Yenisey, M. M., A multi-objective ant colony system algorithm for flow shop scheduling problem, Exp Syst Appl, 37, 1361-1368 (2010)
[43] Ying, K.-C., Solving non-permutation flowshop scheduling problems by an effective iterative greedy heuristic, Int J Adv Manuf Technol, 38, 348-354 (2008)
[44] Ying, K.-C.; Lin, S.-W., Multi-heuristic desirability ant colony system heuristic for non-permutation flowshop scheduling problems, Int J Adv Manuf Technol, 33, 739-802 (2007)
[45] Zobolas, G. I.; Tarantilis, C. D.; Ioannou, G., Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm, Comput Oper Res, 36, 1249-1267 (2009) · Zbl 1160.90490
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.