×

A computationally efficient branch-and-bound algorithm for the permutation flow-shop scheduling problem. (English) Zbl 1441.90061

Summary: In this work we propose an efficient branch-and-bound (B&B) algorithm for the permutation flow-shop problem (PFSP) with makespan objective. We present a new node decomposition scheme that combines dynamic branching and lower bound refinement strategies in a computationally efficient way. To alleviate the computational burden of the two-machine bound used in the refinement stage, we propose an online learning-inspired mechanism to predict promising couples of bottleneck machines. The algorithm offers multiple choices for branching and bounding operators and can explore the search tree either sequentially or in parallel on multi-core CPUs. In order to empirically determine the most efficient combination of these components, a series of computational experiments with 600 benchmark instances is performed. A main insight is that the problem size, as well as interactions between branching and bounding operators substantially modify the trade-off between the computational requirements of a lower bound and the achieved tree size reduction. Moreover, we demonstrate that parallel tree search is a key ingredient for the resolution of large problem instances, as strong super-linear speedups can be observed. An overall evaluation using two well-known benchmarks indicates that the proposed approach is superior to previously published B&B algorithms. For the first benchmark we report the exact resolution – within less than 20 minutes – of two instances defined by 500 jobs and 20 machines that remained open for more than 25 years, and for the second a total of 89 improved best-known upper bounds, including proofs of optimality for 74 of them.

MSC:

90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
65K05 Numerical mathematical programming methods
65Y05 Parallel numerical computation
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Baker, K. R., A comparative study of flow-shop algorithms, Operations Research, 23, 1, 62-73 (1975) · Zbl 0307.90037
[2] Bendjoudi, A.; Melab, N.; Talbi, E.-G., Hierarchical branch and bound algorithm for computational grids, Future Generation Computer Systems, 28, 8, 1168-1176 (2012)
[3] Brown, A. P.G.; Lomnicki, Z. A., Some applications of the “branch-and-bound” algorithm to the machine scheduling problem, Journal of the Operational Research Society, 17, 2, 173-186 (1966)
[4] de Bruin, A.; Kindervater, G. A.P.; Trienekens, H. W.J. M., Asynchronous parallel branch and bound and anomalies, (Ferreira, A.; Rolim, J., Parallel algorithms for irregularly structured problems (1995), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 363-377
[5] Carlier, J.; Rebaï, I., Two branch and bound algorithms for the permutation flow shop problem, European Journal of Operational Research, 90, 2, 238-251 (1996) · Zbl 0913.90162
[6] Chakroun, I.; Melab, N.; Mezmaz, M.; Tuyttens, D., Combining multi-core and GPU computing for solving combinatorial optimization problems, Journal of Parallel and Distributed Computing, 73, 12, 1563-1577 (2013)
[7] Cheng, J.; Kise, H.; Matsumoto, H., A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem, European Journal of Operational Research, 96, 3, 578-590 (1997) · Zbl 0917.90189
[8] Cheng, J.; Kise, H.; Steiner, G.; Stephenson, P., Branch-and-bound algorithms using fuzzy heuristics for solving large-scale flow-shop scheduling problems, (Verdegay, J.-L. (2003), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 21-35) · Zbl 1051.90034
[9] Companys, R.; Mateo, M., Different behaviour of a double branch-and-bound algorithm on FM|PRMU|CMAX and FM|block|CMAX problems, Computers and Operations Research, 34, 4, 938-953 (2007) · Zbl 1107.90016
[10] Daouri, M.; Escobar, F. A.; Xin Chang; Valderrama, C., A hardware architecture for the branch and bound flow-shop scheduling algorithm, Proceedings of the 2015 Norchip international symposium on system-on-chip (SOC) nordic circuits and systems conference (NORCAS):, 1-4 (2015)
[11] Drozdowski, M.; Marciniak, P.; Pawlak, G.; Plaza, M., Grid branch-and-bound for permutation flowshop, (Wyrzykowski, R.; Dongarra, J. J.; Karczewski, K.; Wasniewski, J., Proceedings of the 9th international conference parallel processing and applied mathematics, PPAM 2011, Torun, Poland, September 11-14, 2011. revised selected papers, part II. Proceedings of the 9th international conference parallel processing and applied mathematics, PPAM 2011, Torun, Poland, September 11-14, 2011. revised selected papers, part II, Lecture Notes in Computer Science, 7204 (2011), Springer), 21-30
[12] Dubois-Lacoste, J.; Pagnozzi, F.; Stützle, T., An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem, Computers and Operations Research, 81, 160-166 (2017) · Zbl 1391.90257
[13] Fernandez-Viagas, V.; Ruiz, R.; Framinan, J. M., A new vision of approximate methods for the permutation flowshop to minimise makespan: State-of-the-art and computational evaluation, European Journal of Operational Research, 257, 3, 707-721 (2017) · Zbl 1394.90271
[14] 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, 12, 1243-1255 (2004) · Zbl 1088.90022
[15] www.jstor.org/stable/3689278. · Zbl 0396.90041
[16] Giles, M.; Reguly, I., Trends in high-performance computing for engineering calculations, Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 372, 2022, 20130319 (2014)
[17] Gmys, J.; Leroy, R.; Mezmaz, M.; Melab, N.; Tuyttens, D., Work stealing with private integer vector matrix data structure for multi-core branch-and-bound algorithms, Concurrency and Computation: Practice and Experience, 28, 18, 4463-4484 (2016)
[18] Gmys, J.; Mezmaz, M.; Melab, N.; Tuyttens, D., A gpu-based branch-and-bound algorithm using integer-vector-matrix data structure, Parallel Computing, 59, 119-139 (2016)
[19] Gmys, J., Mezmaz, M., Melab, N., & Tuyttens, D. (2019). Improved upper bounds for permutation flowshop scheduling benchmarks (Taillard and VRF). https://doi.org/10.5281/zenodo.3550553. · Zbl 1441.90061
[20] Hejazi, S. R.; Saghafian, S., Flowshop-scheduling problems with makespan criterion: a review, International Journal of Production Research, 43, 14, 2895-2929 (2005) · Zbl 1068.90059
[21] Ignall, E.; Schrage, L., Application of the branch and bound technique to some flow-shop scheduling problems, Operations Research, 13, 3, 400-412 (1965)
[22] Jin, Y., Surrogate-assisted evolutionary computation: Recent advances and future challenges, Swarm and Evolutionary Computation, 1, 2, 61-70 (2011)
[23] Johnson, S. M., Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, 1, 61-68 (1954) · Zbl 1349.90359
[24] 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
[25] ISBN=9780201896848.
[26] Ladhari, T.; Haouari, M., A computational study of the permutation flow shop problem based on a tight lower bound, Computers and Operations Research, 32, 7, 1831-1847 (2005) · Zbl 1074.90018
[27] Lageweg, B. J.; Lenstra, J. K.; Kan, A. H.G. R., A general bounding scheme for the permutation flow-shop problem, Operations Research, 26, 1, 53-67 (1978) · Zbl 0371.90059
[28] Lemesre, J.; Dhaenens, C.; Talbi, E., An exact parallel method for a bi-objective permutation flowshop problem, European Journal of Operational Research, 177, 3, 1641-1655 (2007) · Zbl 1102.90049
[29] Li, G.; Wah, B. W., Coping with anomalies in parallel branch-and-bound algorithms, IEEE Transactions on Computers, C-35, 6, 568-573 (1986)
[30] Liu, W.; Jin, Y.; Price, M., A new improved NEH heuristic for permutation flowshop scheduling problems, International Journal of Production Economics, 193, 21-30 (2017)
[31] Lomnicki, Z. A., A “branch-and-bound” algorithm for the exact solution of the three-machine scheduling problem, Journal of the Operational Research Society, 16, 1, 89-100 (1965)
[32] http://www.jstor.org/stable/168456.
[33] Melab, N.; Gmys, J.; Mezmaz, M.; Tuyttens, D., Multi-core versus many-core computing for many-task branch-and-bound applied to big optimization problems, Future Generation Computer Systems, 82, 472-481 (2018)
[34] Mezmaz, M.; Leroy, R.; Melab, N.; Tuyttens, D., A multi-core parallel branch-and-bound algorithm using factorial number system, Proceedings of the 2014 IEEE 28th international parallel and distributed processing symposium, 1203-1212 (2014)
[35] Mezmaz, M.; Leroy, R.; Melab, N.; Tuyttens, D., A multi-core parallel branch-and-bound algorithm using factorial number system, Proceedings of the 2014 IEEE 28th international parallel and distributed processing symposium, 1203-1212 (2014)
[36] Mezmaz, M.; Melab, N.; Talbi, E. G., A grid-enabled branch and bound algorithm for solving challenging combinatorial optimization problems, Proceedings of the 2007 IEEE international parallel and distributed processing symposium, Long Beach, CA, 1-9 (2007)
[37] Nabeshima, I., On bound of makespans and its application in m machine scheduling problem, Journal of the Operations Research Society of Japan, 9, 3-4, 98-+ (1967)
[38] Nawaz, M.; Enscore, E. E.; Ham, I., A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega, 11, 1, 91-95 (1983)
[39] Potts, C., An adaptive branching rule for the permutation flow-shop problem, European Journal of Operational Research, 5, 1, 19-25 (1980) · Zbl 0436.90063
[40] Potts, C. N.; Strusevich, V. A., Fifty years of scheduling: a survey of milestones, Journal of the Operational Research Society, 60, sup1, S41-S68 (2009) · Zbl 1168.90311
[41] Ritt, M., A branch-and-bound algorithm with cyclic best-first search for the permutation flow shop scheduling problem, Proceedings of the IEEE international conference on automation science and engineering, CASE 2016, Fort Worth, TX, USA, August 21-25, 2016, 872-877 (2016), IEEE
[42] Rossi, F. L.; Nagano, M. S.; Neto, R. F.T., Evaluation of high performance constructive heuristics for the flow shop with makespan minimization, The International Journal of Advanced Manufacturing Technology, 87, 1, 125-136 (2016)
[43] Ruiz, R.; Maroto, C.; Alcaraz, J., Two new robust genetic algorithms for the flowshop scheduling problem, Omega, 34, 5, 461-476 (2006)
[44] 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
[45] Sutton, R. S.; Barto, A. G., Introduction to reinforcement learning, 135 (1998), MIT Press: MIT Press Cambridge
[46] Szwarc, W., Optimal elimination methods in the m × n flow-shop scheduling problem, Operations Research, 21, 6, 1250-1259 (1973) · Zbl 0274.90020
[47] Taillard, E., Benchmarks for basic scheduling problems, European Journal of Operational Research, 64, 2, 278-285 (1993) · Zbl 0769.90052
[48] Taillard, E. (2015). Flow shop sequencing: Summary of best known lower and upper bounds of Taillard’s instances. http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/flowshop.dir/best_lb_up.txt.
[49] Vallada, E.; Ruiz, R.; Framinan, J. M., New hard benchmark for flowshop scheduling problems minimising makespan, European Journal of Operational Research, 240, 3, 666-677 (2015) · Zbl 1338.90185
[50] Vu, T.-T.; Derbel, B., Parallel branch-and-bound in multi-core multi-cpu multi-GPU heterogeneous environments, Future Generation Computer Systems, 56, 95-109 (2016)
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.