Improved combinatorial Benders decomposition for a scheduling problem with unrelated parallel machines. (English) Zbl 1437.90077
J. Appl. Math. 2017, Article ID 9452762, 10 p. (2017); corrigendum ibid. 2017, Article ID 2465891, 2 p. (2017).
Summary: This paper addresses the unrelated parallel machines scheduling problem with sequence and machine dependent setup times. Its goal is to minimize the makespan. The problem is solved by a combinatorial Benders decomposition. This method can be slow to converge. Therefore, three procedures are introduced to accelerate its convergence. The first procedure is a new method that consists of terminating the execution of the master problem when a repeated optimal solution is found. The second procedure is based on the multicut technique. The third procedure is based on the warm-start. The improved Benders decomposition scheme is compared to a mathematical formulation and a standard implementation of Benders decomposition algorithm. In the experiments, two test sets from the literature are used, with 240 and 600 instances with up to 60 jobs and 5 machines. For the first set the proposed method performs 21.85% on average faster than the standard implementation of the Benders algorithm. For the second set the proposed method failed to find an optimal solution in only 31 in 600 instances, obtained an average gap of 0.07%, and took an average computational time of 377.86 s, while the best results of the other methods were 57, 0.17%, and 573.89 s, respectively.
References:
| [1] | Avalos-Rosales, O.; Angel-Bello, F.; Alvarez, A., Efficient metaheuristic algorithm and re-formulations for the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times, International Journal of Advanced Manufacturing Technology, 76, 9-12, 1705-1718 (2014) · doi:10.1007/s00170-014-6390-6 |
| [2] | Afzalirad, M.; Shafipour, M., Design of an efficient genetic algorithm for resource-constrained unrelated parallel machine scheduling problem with machine eligibility restrictions, Journal of Intelligent Manufacturing (2015) · doi:10.1007/s10845-015-1117-6 |
| [3] | Mokotoff, E., Parallel machine scheduling problems: a survey, Asia-Pacific Journal of Operational Research, 18, 2, 193-242 (2001) · Zbl 1042.90564 |
| [4] | Allahverdi, A.; Soroush, H. M., The significance of reducing setup times/setup costs, European Journal of Operational Research, 187, 3, 978-984 (2008) · Zbl 1137.90475 · doi:10.1016/j.ejor.2006.09.010 |
| [5] | Błażewicz, J.; Ecker, K. H.; Pesch, E.; Schmidt, G.; Weglarz, J., Scheduling Computer and Manufacturing Processes (1996), Berlin, Germany: Springer Berlin Heidelberg, Berlin, Germany · Zbl 0911.90201 · doi:10.1007/978-3-662-03217-6 |
| [6] | Rocha, P. L.; Ravetti, M. G.; Mateus, G. R.; Pardalos, P. M., Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times, Computers and Operations Research, 35, 4, 1250-1264 (2008) · Zbl 1169.90010 · doi:10.1016/j.cor.2006.07.015 |
| [7] | de Paula, M. R.; Mateus, G. R.; Ravetti, M. G., A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times, Computers & Operations Research, 37, 5, 938-949 (2010) · Zbl 1177.90196 · doi:10.1016/j.cor.2009.07.006 |
| [8] | Tran, T.; Beck, J. C., Logic-based Benders decomposition for alternative resource scheduling with sequence dependent setups, Proceedings of the 20th European Conference on Artificial Intelligence (ECAI ’12) · Zbl 1327.90075 |
| [9] | de Paula, M. R.; Ravetti, M. n.; Mateus, G. R.; Pardalos, P. M., Solving parallel machines scheduling problems with sequence-dependent setup times using variable neighbourhood search, IMA Journal of Management Mathematics, 18, 2, 101-115 (2007) · Zbl 1177.90151 · doi:10.1093/imaman/dpm016 |
| [10] | Lin, S.-W.; Lu, C.-C.; Ying, K.-C., Minimization of total tardiness on unrelated parallel machines with sequence- and machine-dependent setup times under due date constraints, International Journal of Advanced Manufacturing Technology, 53, 1-4, 353-361 (2011) · doi:10.1007/s00170-010-2824-y |
| [11] | Vallada, E.; Ruiz, R., A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times, European Journal of Operational Research, 211, 3, 612-622 (2011) · doi:10.1016/j.ejor.2011.01.011 |
| [12] | Ying, K.-C.; Lee, Z.-J.; Lin, S.-W., Makespan minimization for scheduling unrelated parallel machines with setup times, Journal of Intelligent Manufacturing, 23, 5, 1795-1803 (2012) · doi:10.1007/s10845-010-0483-3 |
| [13] | Lee, J.-H.; Yu, J.-M.; Lee, D.-H., A tabu search algorithm for unrelated parallel machine scheduling with sequence- and machine-dependent setups: Minimizing total tardiness, International Journal of Advanced Manufacturing Technology, 69, 9-12, 2081-2089 (2013) · doi:10.1007/s00170-013-5192-6 |
| [14] | Arnaout, J.-P.; Musa, R.; Rabadi, G., A two-stage ant colony optimization algorithm to minimize the makespan on unrelated parallel machines—Part II: enhancements and experimentations, Journal of Intelligent Manufacturing, 25, 1, 43-53 (2014) · doi:10.1007/s10845-012-0672-3 |
| [15] | Hooker, J. N., A hybrid method for planning and scheduling, Constraints. An International Journal, 10, 4, 385-401 (2005) · Zbl 1122.90054 · doi:10.1007/s10601-005-2812-2 |
| [16] | Hooker, J. N., An integrated method for planning and scheduling to minimize tardiness, Constraints. An International Journal, 11, 2-3, 139-157 (2006) · Zbl 1103.68811 · doi:10.1007/s10601-006-8060-2 |
| [17] | Hooker, J. N., Planning and scheduling by logic-based Benders decomposition, Operations Research, 55, 3, 588-602 (2007) · Zbl 1167.90512 · doi:10.1287/opre.1060.0371 |
| [18] | Li, H.; Womer, K., Scheduling projects with multi-skilled personnel by a hybrid {MILP}/{CP} benders decomposition algorithm, Journal of Scheduling, 12, 3, 281-298 (2009) · Zbl 1185.90112 · doi:10.1007/s10951-008-0079-3 |
| [19] | Coban, E.; Hooker, J. N., Single-facility scheduling by logic-based Benders decomposition, Annals of Operations Research, 210, 245-272 (2013) · Zbl 1284.90023 · doi:10.1007/s10479-011-1031-z |
| [20] | Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik, 4, 238-252 (1962) · Zbl 0109.38302 · doi:10.1007/BF01386316 |
| [21] | Hooker, J. N.; Ottosson, G., Logic-based Benders decomposition, Mathematical Programming, Series B, 96, 1, 33-60 (2003) · Zbl 1023.90082 · doi:10.1007/s10107-003-0375-9 |
| [22] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H., Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |
| [23] | Saharidis, G. K. D.; Ierapetritou, M. G., Improving benders decomposition using maximum feasible subsystem (MFS) cut generation strategy, Computers and Chemical Engineering, 34, 8, 1237-1245 (2010) · doi:10.1016/j.compchemeng.2009.10.002 |
| [24] | Sherali, H. D.; Lunday, B. J., On generating maximal nondominated Benders cuts, Annals of Operations Research, 210, 57-72 (2013) · Zbl 1288.90055 · doi:10.1007/s10479-011-0883-6 |
| [25] | Papadakos, N., Practical enhancements to the Magnanti-Wong method, Operations Research Letters, 36, 4, 444-449 (2008) · Zbl 1155.90432 · doi:10.1016/j.orl.2008.01.005 |
| [26] | Rei, W.; Cordeau, J.-F.; Gendreau, M.; Soriano, P., Accelerating Benders decomposition by local branching, INFORMS Journal on Computing, 21, 2, 333-345 (2009) · Zbl 1243.90122 · doi:10.1287/ijoc.1080.0296 |
| [27] | Saharidis, G. K.; Minoux, M.; Ierapetritou, M. G., Accelerating Benders method using covering cut bundle generation, International Transactions in Operational Research, 17, 2, 221-237 (2010) · Zbl 1279.90072 · doi:10.1111/j.1475-3995.2009.00706.x |
| [28] | Saharidis, G. K.; Ierapetritou, M. G., Speed-up Benders decomposition using maximum density cut ({MDC}) generation, Annals of Operations Research, 210, 101-123 (2013) · Zbl 1284.90043 · doi:10.1007/s10479-012-1237-8 |
| [29] | Azad, N.; Saharidis, G. K.; Davoudpour, H.; Malekly, H.; Yektamaram, S. A., Strategies for protecting supply chain networks against facility and transportation disruptions: an improved Benders decomposition approach, Annals of Operations Research, 210, 125-163 (2013) · Zbl 1284.90033 · doi:10.1007/s10479-012-1146-x |
| [30] | McDaniel, D.; Devine, M., A modified benders’ partitioning algorithm for mixed integer programming, Management Science, 24, 3, 312-319 (1977) · Zbl 0371.90102 · doi:10.1287/mnsc.24.3.312 |
| [31] | Wheatley, D.; Gzara, F.; Jewkes, E., Logic-based Benders decomposition for an inventory-location problem with service constraints, Omega (United Kingdom), 55, 10-23 (2015) · doi:10.1016/j.omega.2015.02.001 |
| [32] | Geoffrion, A. M.; Graves, G. W., Multicommodity distribution system design by benders decomposition, Management Science, 20, 5, 822-844 (1974) · Zbl 0304.90122 · doi:10.1287/mnsc.20.5.822 |
| [33] | Côté, G.; Laughton, M. A., Large-scale mixed integer programming: benders-type heuristics, European Journal of Operational Research, 16, 3, 327-333 (1984) · Zbl 0532.90077 · doi:10.1016/0377-2217(84)90287-X |
| [34] | Fischetti, M.; Lodi, A., Local branching, Mathematical Programming. A Publication of the Mathematical Programming Society, 98, 1-3, Ser. B, 23-47 (2003) · Zbl 1060.90056 · doi:10.1007/s10107-003-0395-5 |
| [35] | Poojari, C. A.; Beasley, J. E., Improving Benders decomposition using a genetic algorithm, European Journal of Operational Research, 199, 1, 89-97 (2009) · Zbl 1176.90428 · doi:10.1016/j.ejor.2008.10.033 |
| [36] | Huang, Z.; Zheng, Q. P., Decomposition-based exact algorithms for risk-constrained traveling salesman problems with discrete random arc costs, Optimization Letters, 9, 8, 1553-1568 (2015) · Zbl 1335.90082 · doi:10.1007/s11590-014-0798-7 |
| [37] | Sherali, H. D.; Bae, K.-H.; Haouari, M., A Benders decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture, Annals of Operations Research, 210, 213-244 (2013) · Zbl 1284.90026 · doi:10.1007/s10479-011-0906-3 |
| [38] | Jenabi, M.; Fatemi Ghomi, S. M.; Torabi, S. A.; Hosseinian, S. H., Acceleration strategies of Benders decomposition for the security constraints power system expansion planning, Annals of Operations Research, 235, 337-369 (2015) · Zbl 1332.90177 · doi:10.1007/s10479-015-1983-5 |
| [39] | You, F.; Grossmann, I. E., Multicut Benders decomposition algorithm for process supply chain planning under uncertainty, Annals of Operations Research, 210, 191-211 (2013) · Zbl 1284.90046 · doi:10.1007/s10479-011-0974-4 |
| [40] | Magnanti, T. L.; Wong, R. T., Accelerating Benders decomposition: algorithmic enhancement and model selection criteria, Operations Research. The Journal of the Operations Research Society of America, 29, 3, 464-484 (1981) · Zbl 0455.90064 · doi:10.1287/opre.29.3.464 |
| [41] | Jain, V.; Grossmann, I. E., Algorithms for hybrid MILP/CP models for a class of optimization problems, INFORMS Journal on Computing, 13, 4, 258-276 (2001) · Zbl 1238.90106 · doi:10.1287/ijoc.13.4.258.9733 |
| [42] | Hall, L. A.; Schulz, A. S.; Shmoys, D. B.; Wein, J., Scheduling to minimize average completion time: off-line and on-line approximation algorithms, Mathematics of Operations Research, 22, 3, 513-544 (1997) · Zbl 0883.90064 · doi:10.1287/moor.22.3.513 |
| [43] | Phillips, C.; Stein, C.; Wein, J., Minimizing average completion time in the presence of release dates, Mathematical Programming, 82, 1-2, Ser. B, 199-223 (1998) · Zbl 0920.90074 · doi:10.1007/BF01585872 |
| [44] | van den Akker, J. M.; van Hoesel, C. P.; Savelsbergh, M. W., A polyhedral approach to single-machine scheduling problems, Mathematical Programming. A Publication of the Mathematical Programming Society, 85, 3, Ser. A, 541-572 (1999) · Zbl 1072.90523 · doi:10.1007/s101070050071 |
| [45] | Fanjul-Peyro, L.; Ruiz, R., Size-reduction heuristics for the unrelated parallel machines scheduling problem, Computers and Operations Research, 38, 1, 301-309 (2011) · doi:10.1016/j.cor.2010.05.005 |
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.
