Reduction of permutation flowshop problems to single machine problems using machine dominance relations. (English) Zbl 1391.90259
Summary: The permutation flowshop scheduling problem with makespan objective (PFSP-M) is known to be NP-hard for more than two machines, and literally hundreds of works in the last decades have proposed exact and approximate algorithms to solve it. These works – of computational/experimental nature – show that the PFSP-M is also empirically hard, in the sense that optimal or quasi-optimal sequences statistically represent a very small fraction of the space of feasible solutions, and that there are big differences among the corresponding makespan values. In the vast majority of these works, it has been assumed that (a) processing times are not job- and/or machine-correlated, and (b) all machines are initially available. However, some works have found that the problem turns to be almost trivial (i.e., almost every sequence yields an optimal or quasi-optimal solution) if one of these assumptions is dropped. To the best of our knowledge, no theoretical or experimental explanation has been proposed by this rather peculiar fact. Our hypothesis is that, under certain conditions of machine availability, or correlated processing times, the performance of a given sequence in a flowshop is largely determined by only one stage, thus effectively transforming the flowshop layout into a single machine. Since the single machine scheduling problem with makespan objective is a trivial problem where all feasible sequences are optimal, it would follow that, under these conditions, the equivalent PFSP-M is almost trivial. To address this working hypothesis from a general perspective, we investigate some conditions that allow reducing a permutation flowshop scheduling problem to a single machine scheduling problem, focusing on the two most common objectives in the literature, namely makespan and flowtime. Our work is a combination of theoretical and computational analysis, therefore several properties are derived to prove the conditions for an exact (theoretical) equivalence, together with an extensive computational evaluation to establish an empirical equivalence.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C60 | Abstract computational complexity for mathematical programming problems |
Keywords:
scheduling; flowshop; processing times; PFSP; makespan; flowtime; single machine; dominating machineReferences:
| [1] | Carlier, J., Ordonnancements a contraintes disjonctives, RAIRO Recherche Operationnelle, 12, 4, 333-350, (1978) · Zbl 0401.90052 |
| [2] | Cepek, O.; Okada, M.; Vlach, M., Nonpreemptive flowshop scheduling with machine dominance, Eur J Oper Res, 139, 2, 245-261, (2002) · Zbl 1001.90032 |
| [3] | Cheng, M.; Sun, S.; Yu, Y., A note on flow shop scheduling problems with a learning effect on no-idle dominant machines, Appl Math Comput, 184, 2, 945-949, (2007) · Zbl 1143.90011 |
| [4] | Demirkol, E.; Mehta, S.; Uzsoy, R., Benchmarks for shop scheduling problems, Eur J Oper Res, 109, 1, 137-141, (1998) · Zbl 0951.90022 |
| [5] | Dong, X.; Chen, P.; Huang, H.; Nowak, M., A multi-restart iterated local search algorithm for the permutation flow shop problem minimizing total flow time, Comput Oper Res, 40, 2, 627-632, (2013) · Zbl 1349.90339 |
| [6] | Dudek, R.; Teuton, O., Development of m stage decision rule for scheduling n jobs through m machines, Oper Res, 12, 471, (1964) · Zbl 0208.45704 |
| [7] | Easwaran, G.; Parten, L.; Moras, R.; Uhlig, P., Makespan minimization in machine dominated flowshop, Appl Math Comput, 217, 1, 110-116, (2010) · Zbl 1230.90088 |
| [8] | Fernandez-Viagas, V.; Framinan, J., A new set of high-performing heuristics to minimise flowtime in permutation flowshops, Comput Oper Res, 53, 68-80, (2015) · Zbl 1348.90257 |
| [9] | Fernandez-Viagas, V.; Framinan, J., NEH-based heuristics for the permutation flowshop scheduling problem to minimise total tardiness, Comput Oper Res, 60, 27-36, (2015) · Zbl 1348.90258 |
| [10] | Fernandez-Viagas, V.; Framinan, J. M., On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem, Comput Oper Res, 45, 0, 60-67, (2014) · Zbl 1348.90256 |
| [11] | Framinan, J.; Gupta, J.; Leisten, R., A review and classification of heuristics for permutation flow-shop scheduling with makespan objective, J Oper Res Soc, 55, 12, 1243-1255, (2004) · Zbl 1088.90022 |
| [12] | Framinan, J.; Leisten, R., A heuristic for scheduling a permutation flowshop with makespan objective subject to maximum tardiness, Int J Prod Econ, 99, 1-2, 28-40, (2006) |
| [13] | Framinan, J.; Leisten, R.; Ruiz-Usano, R., Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation, Eur J Oper Res, 141, 3, 559-569, (2002) · Zbl 1081.90555 |
| [14] | Framinan, J.; Leisten, R.; Ruiz-Usano, R., Comparison of heuristics for flowtime minimisation in permutation flowshops, Comput Oper Res, 32, 5, 1237-1254, (2005) · Zbl 1074.90017 |
| [15] | Gajpal, Y.; Rajendran, C., An ant-colony optimization algorithm for minimizing the completion-time variance of jobs in flowshops, Int J Prod Econ, 101, 2, 259-272, (2006) |
| [16] | Garey, M.; Johnson, D.; Sethi, R., Complexity of flowshop and jobshop scheduling, Math Oper Res, 1, 2, 117-129, (1976) · Zbl 0396.90041 |
| [17] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and schedulinga survey, Ann Discrete Math, 5, 287-326, (1979) · Zbl 0411.90044 |
| [18] | Heller, J., Some numerical experiments for an m x j flow shop and its decision-theoretical aspects, Oper Res, 8, 2, 178-184, (1960) · Zbl 0092.27910 |
| [19] | Ho, J.; Gupta, J., Flowshop scheduling with dominant machines, Comput Oper Res, 22, 2, 237-246, (1995) · Zbl 0826.90064 |
| [20] | Holm, S., A simple sequentially rejective multiple test procedure, Scand J Stat, 6, 65-70, (1979) · Zbl 0402.62058 |
| [21] | Johnson, S., Optimal two- and three-stage production schedules with setup times included, Naval Res Logist Q, 1, 1, 61-68, (1954) · Zbl 1349.90359 |
| [22] | Leisten, R.; Rajendran, C., Variability of completion time differences in permutation flow shop scheduling, Comput Oper Res, 54, 155-167, (2014) · Zbl 1348.90284 |
| [23] | M’Hallah, R., An iterated local search variable neighborhood descent hybrid heuristic for the total earliness tardiness permutation flow shop, Int J Prod Res, 52, 13, 3802-3819, (2014) |
| [24] | Monma, C. L.; Rinnooy Kan, A. H.G., A concise survey of efficiently solvable special cases of the permutation flow-shop problem, RAIRO—Oper Res—Recherche Opérationnelle, 17, 2, 105-119, (1983) · Zbl 0523.90054 |
| [25] | Nawaz, M.; Enscore, E.; Ham, I., A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, OMEGA Int J Manag Sci, 11, 1, 91-95, (1983) |
| [26] | Pan, Q.-K.; Ruiz, R., A comprehensive review and evaluation of permutation flowshop heuristics to minimize flowtime, Comput Oper Res, 40, 1, 117-128, (2013) · Zbl 1349.90386 |
| [27] | Perez-Gonzalez, P.; Framinan, J., Scheduling permutation flowshops with initial availability constraintanalysis of solutions and constructive heuristics, Comput Oper Res, 36, 10, 2866-2876, (2009) · Zbl 1160.90481 |
| [28] | Pinedo, M., Scheduling: theory, algorithms, and systems, (2012), Springer US, New York · Zbl 1239.90002 |
| [29] | Rad, S. F.; Ruiz, R.; Boroojerdian, N., New high performing heuristics for minimizing makespan in permutation flowshops, OMEGA Int J Manag Sci, 37, 2, 331-345, (2009) |
| [30] | Reeves, C., A genetic algorithm for flowshop sequencing, Comput Oper Res, 22, 1, 5-13, (1995) · Zbl 0815.90097 |
| [31] | Reza Hejazi, S.; Saghafian, S., Flowshop-scheduling problems with makespan criteriona review, Int J Prod Res, 43, 14, 2895-2929, (2005) · Zbl 1068.90059 |
| [32] | Rinnooy Kan AHG. Machine scheduling problems: classification, complexity and computations. The Hague: Martinus Nijhoff; 1976. |
| [33] | Ruiz, R.; Maroto, C., A comprehensive review and evaluation of permutation flowshop heuristics, Eur J Oper Res, 165, 2, 479-494, (2005) · Zbl 1066.90038 |
| [34] | Schaller, J.; Valente, J., A comparison of metaheuristic procedures to schedule jobs in a permutation flow shop to minimise total earliness and tardiness, Int J Prod Res, 51, 3, 772-779, (2013) |
| [35] | Sun, Y.; Zhang, C.; Gao, L.; Wang, X., Multi-objective optimization algorithms for flow shop scheduling problema review and prospects, Int J Adv Manuf Technol, 55, 5-8, 723-739, (2011) |
| [36] | Taillard, E., Benchmarks for basic scheduling problems, Eur J Oper Res, 64, 2, 278-285, (1993) · Zbl 0769.90052 |
| [37] | Vallada, E.; Ruiz, R., Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem, Omega, 38, 12, 57-67, (2010) |
| [38] | Vallada, E.; Ruiz, R.; Framinan, J., New hard benchmark for flowshop scheduling problems minimising makespan, Eur J Oper Res, 240, 666-677, (2015) · Zbl 1338.90185 |
| [39] | Vallada, E.; Ruiz, R.; Minella, G., Minimising total tardiness in the m-machine flowshop problema review and evaluation of heuristics and metaheuristics, Comput Oper Res, 35, 4, 1350-1373, (2008) · Zbl 1179.90160 |
| [40] | Wang, J.-B.; Shan, F.; Jiang, B.; Wang, L.-Y., Permutation flow shop scheduling with dominant machines to minimize discounted total weighted completion time, Appl Math Comput, 182, 1, 947-954, (2006), cited By 9 · Zbl 1116.90049 |
| [41] | Watson, J.; Barbulescu, L.; Whitley, L.; Howe, A., Contrasting structured and random permutation flow-shop scheduling problemssearch-space topology and algorithm performance, INFORMS J Comput, 14, 2, 98-123, (2002) · Zbl 1238.90072 |
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.
