Hybrid matheuristics to solve the integrated lot sizing and scheduling problem on parallel machines with sequence-dependent and non-triangular setup. (English) Zbl 1487.90012
Summary: This paper approaches the integrated lot sizing and scheduling problem (ILSSP), in which non-identical machines work in parallel with non-triangular sequence-dependent setup costs and times, setup carry-over and capacity limitation. The aim of the studied ILSSP, here called ILSSP-NT on parallel machines, is to determine a production planning and tasks sequencing that meet period demands without delay and in such a way that the total costs of production, machine setup and inventory are minimized. The dearth of literature on the ILSSP-NT, despite the increasing amount of applications in the industrial sector, mainly in the food processing industry, motivated us to conduct this study. In this paper, we propose efficient methods to solve the ILSSP-NT on parallel machines. The methods virtually consist in the hybridization of the relax-and-fix and fix-and-optimize methods with the path-relinking and kernel search heuristics. To assess how well the heuristics solve the ILSSP-NT on parallel machines, we compared their results with those of the CPLEX solver with a fixed CPU time limit. The proposed matheuristics significantly outperformed CPLEX in most of the tested instances.
MSC:
| 90B05 | Inventory, storage, reservoirs |
| 90B35 | Deterministic scheduling theory in operations research |
| 90B30 | Production models |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Alltech (2018). 2018 Alltech Global Feed Survey estimates world feed production in excess of 1 billion metric tons for second consecutive year. Alltech. https://www.alltech.com/news/ Accessed 08 August 2018. |
| [2] | Almada-Lobo, B.; James, R. J., Neighbourhood search meta-heuristics for capacitated lot-sizing with sequence-dependent setups, International Journal of Production Research, 48, 3, 861-878 (2010) · Zbl 1197.90190 |
| [3] | Angelelli, E.; Mansini, R.; Speranza, M., Kernel Search: A heuristic framework for MILP problems with binary variables, Technical report, RT 2007-04-56 (2007), Department of Electronics for Automation, University of Brescia |
| [4] | Angelelli, E.; Mansini, R.; Speranza, M. G., Kernel Search: A general heuristic for the multi-dimensional knapsack problem, Computers & Operations Research, 37, 11, 2017-2026 (2010) · Zbl 1188.90207 |
| [5] | de Araujo, S. A.; Arenales, M. N.; Clark, A. R., Joint rolling-horizon scheduling of materials processing and lot-sizing with sequence-dependent setups, Journal of Heuristics, 13, 4, 337-358 (2007) |
| [6] | Baker, T.; Muckstadt Jr, J., The CHES problems, Providence (1989) |
| [7] | Bertsekas, D. P.; Tseng, P., Relaxation methods for minimum cost ordinary and generalized network flow problems, Operations Research, 36, 1, 93-114 (1988) · Zbl 0662.90027 |
| [8] | Bilde, O.; Krarup, J., Sharp lower bounds and efficient algorithms for the simple plant location problem, Annals of Discrete Mathematics, 1, 79-97 (1977) · Zbl 0364.90068 |
| [9] | Boonmee, A.; Sethanan, K., A GLNPSO for multi-level capacitated lot-sizing and scheduling problem in the poultry industry, European Journal of Operational Research, 250, 2, 652-665 (2016) · Zbl 1346.90015 |
| [10] | Buschkühl, L.; Sahling, F.; Helber, S.; Tempelmeier, H., Dynamic capacitated lot- sizing problems: A classification and review of solution approaches., OR Spectrum, 32, 2, 231-261 (2010) · Zbl 1183.90162 |
| [11] | Carvalho, D. M.; Nascimento, M. C.V., Lagrangian heuristics for the capacitated multi-plant lot sizing problem with multiple periods and items, Computers & Operations Research, 71, 137-148 (2016) · Zbl 1349.90014 |
| [12] | Carvalho, D. M.; Nascimento, M. C.V., A kernel search to the multi-plant capacitated lot sizing problem with setup carry-over, Computers & Operations Research, 100, 43-53 (2018) · Zbl 1458.90227 |
| [13] | Claassen, G.; Gerdessen, J. C.; Hendrix, E. M.; van der Vorst, J. G., On production planning and scheduling in food processing industry: Modelling non-triangular setups and product decay, Computers & Operations Research, 76, 147-154 (2016) · Zbl 1349.90279 |
| [14] | Clark, A.; Almada-Lobo, B.; Almeder, C., Lot sizing and scheduling: Industrial extensions and research opportunities, International Journal of Production Research, 49, 9, 2457-2461 (2011) |
| [15] | Clark, A.; Mahdieh, M.; Rangel, S., Production lot sizing and scheduling with non-triangular sequence-dependent setup times, International Journal of Production Research, 52, 8, 2490-2503 (2014) |
| [16] | Clark, A. R.; Morabito, R.; Toso, E. A., Production setup-sequencing and lot-sizing at an animal nutrition plant through ATSP subtour elimination and patching, Journal of Scheduling, 13, 2, 111-121 (2010) · Zbl 1184.90058 |
| [17] | Copil, K.; Wörbelauer, M.; Meyr, H.; Tempelmeier, H., Simultaneous lotsizing and scheduling problems: A classification and review of models, OR Spectrum, 39, 1, 1-64 (2017) · Zbl 1368.90065 |
| [18] | Cplex, I. I. (2017). IBMILOGCPLEXoptimization studio getting started with CPLEX version 12.7.1. |
| [19] | Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Mathematical Programming, Series A, 91, 201-213 (2002) · Zbl 1049.90004 |
| [20] | Drexl, A.; Kimms, A., Lot sizing and scheduling - Survey and extensions, European Journal of Operational Research, 99, 2, 221-235 (1997) · Zbl 0923.90067 |
| [21] | Dueck, G.; Scheuer, T., Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing, Journal of Computational Physics, 90, 1, 161-175 (1990) · Zbl 0707.65039 |
| [22] | Federation, I. F. I. (2016). Global feed statistics. IFIF - International Feed Industry Federation. http://annualreport.ifif.org/. Accessed 08 August 2018http://annualreport.ifif.org/. |
| [23] | Ferreira, D.; Morabito, R.; Rangel, S., Solution approaches for the soft drink integrated production lot sizing and scheduling problem, European Journal of Operational Research, 196, 2, 697-706 (2009) · Zbl 1163.90832 |
| [24] | Florian, M.; Lenstra, J. K.; Rinnoy Kan, A. H.G., Deterministic production planning algorithms and complexity, Management Science, 26, 7, 669-679 (1980) · Zbl 0445.90025 |
| [25] | Glover, F., A template for scatter search and path relinking, (Hao, J.-K.; Lutton, E.; Ronald, E.; Schoenauer, M.; Snyers, D., Artificial evolution (1998), Springer: Springer Berlin, Heidelberg), 1-51 |
| [26] | Glover, F.; Laguna, M., Tabu Search, 2093-2229 (1998), Springer US: Springer US Boston, MA |
| [27] | Glover, F.; Laguna, M., Fundamentals of scatter search and path relinking, Control and Cybernetics, 29, 3, 653-684 (2000) · Zbl 0983.90077 |
| [28] | Guastaroba, G.; Savelsbergh, M.; Speranza, M. G., Adaptive Kernel Search: A heuristic for solving mixed integer linear programs, European Journal of Operational Research, 263, 3, 789-804 (2017) · Zbl 1380.90290 |
| [29] | Guimarães, L.; Klabjan, D.; Almada-Lobo, B., Pricing, relaxing and fixing under lot sizing and scheduling, European Journal of Operational Research, 230, 2, 399-411 (2013) · Zbl 1317.90123 |
| [30] | Guimarães, L.; Klabjan, D.; Almada-Lobo, B., Modeling lotsizing and scheduling problems with sequence dependent setups, European Journal of Operational Research, 239, 3, 644-662 (2014) · Zbl 1339.90027 |
| [31] | Helber, S.; Sahling, F., A fix-and-optimize approach for the multi-level capacitated lot sizing problem, International Journal of Production Economics, 123, 2, 247-256 (2010) |
| [32] | James, R. J.; Almada-Lobo, B., Single and parallel machine capacitated lotsizing and scheduling: New iterative MIP-based neighborhood search heuristics, Computers & Operations Research, 38, 12, 1816-1825 (2011) · Zbl 1215.90027 |
| [33] | Jans, R.; Degraeve, Z., Modeling industrial lot sizing problems: A review, International Journal of Production Research, 46, 6, 1619-1643 (2008) · Zbl 1160.90407 |
| [34] | Kang, S.; Malik, K.; Thomas, L. J., Lotsizing and scheduling on parallel machines with sequence-dependent setup costs, Management Science, 45, 2, 273-289 (1999) · Zbl 1231.90201 |
| [35] | Karimi, B.; Ghomi, S. M.T. F.; Wilson, J. M., The capacitated lot sizing problem: A review of models and algorithms, Omega, 31, 5, 365-378 (2003) |
| [36] | Karp, R. M., A patching algorithm for the nonsymmetric traveling-salesman problem, SIAM Journal on Computing, 8, 4, 561-573 (1979) · Zbl 0427.90064 |
| [37] | Kirkpatrick, S.; Vecchi, M. P., Optimization by simmulated annealing, Science, 220, 4598, 671-680 (1983) · Zbl 1225.90162 |
| [38] | Maes, J.; McClain, J. O.; Wassenhove, L. N.V., Multilevel capacitated lotsizing complexity and LP-based heuristics, European Journal of Operational Research, 53, 2, 131-148 (1991) · Zbl 0734.90036 |
| [39] | Marinelli, F.; Nenni, M. E.; Sforza, A., Capacitated lot sizing and scheduling with parallel machines and shared buffers: A case study in a packaging company, Annals of Operations Research, 150, 1, 177-192 (2007) · Zbl 1144.90388 |
| [40] | Martínez, K. P.; Adulyasak, Y.; Jans, R.; Morabito, R.; Toso, E. A.V., An exact optimization approach for an integrated process configuration, lot-sizing, and scheduling problem, Computers & Operations Research, 103, 310-323 (2019) · Zbl 1458.90345 |
| [41] | Menezes, A. A.; Clark, A.; Almada-Lobo, B., Capacitated lot-sizing and scheduling with sequence-dependent, period-overlapping and non-triangular setups, Journal of Scheduling, 14, 2, 209-219 (2011) · Zbl 1213.90124 |
| [42] | Meyr, H., Simultaneous lotsizing and scheduling on parallel machines, European Journal of Operational Research, 139, 2, 277-292 (2002) · Zbl 1001.90034 |
| [43] | Nascimento, M. C.V.; Resende, M. C.G.; Toledo, F. M.B., GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem, European Journal of Operational Research, 200, 3, 747-754 (2010) · Zbl 1177.90348 |
| [44] | Pochet, Y.; Wolsey, L. A., Production planning by mixed integer programming (2006), Springer Science & Business Media · Zbl 1102.90039 |
| [45] | Sahling, F.; Buschkühl, L.; Tempelmeier, H.; Helber, S., Solving a multi-level capacitated lot sizing problem with multi-period setup carry-over via a fix-and-optimize heuristic, Computers & Operations Research, 36, 9, 2546-2553 (2009) · Zbl 1179.90018 |
| [46] | Student, The probable error of a mean, Biometrika, 1-25 (1908) · Zbl 1469.62201 |
| [47] | Toso, E. A.; Morabito, R.; Clark, A. R., Lot sizing and sequencing optimisation at an animal-feed plant, Computers & Industrial Engineering, 57, 3, 813-821 (2009) |
| [48] | Xiao, J.; Yang, H.; Zhang, C.; Zheng, L.; Gupta, J. N., A hybrid Lagrangian-simulated annealing-based heuristic for the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times, Computers & Operations Research, 63, 72-82 (2015) · Zbl 1349.90053 |
| [49] | Zhu, X.; Wilhelm, W. E., Scheduling and lot sizing with sequence-dependent setup: A literature review, IIE Transactions, 38, 11, 987-1007 (2006) |
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.
