Abstract
Cutting stock and bin packing problems are common in several industrial sectors, such as paper, glass, furniture, steel industry, construction, transportation, among others. The classical cutting stock problem (CSP) ignores the production planning and scheduling of multiple customer orders. Nevertheless, in real industrial settings customer orders have to be planned and scheduled over time so as to meet demand and required due dates. We propose an integer linear programming model for the one-dimensional cutting stock and scheduling problem with heterogeneous orders. As this problem is a generalization of the classical single-period one-dimensional CSP, which is known to be NP-hard, it is difficult to solve real-sized instances to optimality. Thus, we propose a novel matheuristic algorithm based on a fix-and-optimize strategy hybridized with a random local search. The proposed matheuristic was tested on a set of 160 synthetic problem instances based on a real-world problem and compared with CPLEX solver. In larger instances, the proposed matheuristic performed better than CPLEX, with average relative percentage deviation (RPD) regarding objective values as high as 72%. On the other hand, in small instances CPLEX showed a marginal advantage, with best average RPD of 18% with relation to the matheuristic. We also performed a paired t-test with significance level 0.05 and null hypothesis: no difference between the proposed matheuristic and CPLEX. In small test instances, the performance of the proposed matheuristic was statistically indistinguishable from CPLEX, while in larger instances the matheuristic outperformed CPLEX in most cases with \(p\,\text {value} < 0.05\).
Similar content being viewed by others
References
Arbib C, Marinelli F (2005) Integrating process optimization and inventory planning in cutting-stock with skiving option: an optimization model and its application. Eur J Oper Res 163(3):617–630. https://doi.org/10.1016/j.ejor.2003.12.021
Arbib C, Marinelli F (2014) On cutting stock with due dates. Omega 46:11–20. https://doi.org/10.1016/j.omega.2014.01.004
Archetti C, Speranza MG (2014) A survey on matheuristics for routing problems. EURO J Comput Optim 2(4):223–246. https://doi.org/10.1007/s13675-014-0030-7
Braga N, Alves C, Macedo R, de Carvalho JV (2015) A model-based heuristic for the combined cutting stock and scheduling problem. In: Gervasi O et al (eds) Computational science and its applications – ICCSA 2015. ICCSA 2015. Lecture Notes in Computer Science, vol 9156. Springer, Cham
Braga N, Alves C, de Carvalho J (2016a) Exact solution of combined cutting stock and scheduling problems. Lect Notes Econ Math 682:131–139
Braga N, Alves C, Macedo R, de Carvalho JV (2016b) Combined cutting stock and scheduling: a matheuristic approach. Int J Innov Comput Appl 7(3):135–146. https://doi.org/10.1504/IJICA.2016.078724
Della Croce F, Salassa F (2014) A variable neighborhood search based matheuristic for nurse rostering problems. Ann Oper Res 218(1):185–199. https://doi.org/10.1007/s10479-012-1235-x
Dyckhoff H (1990) Cutting and packing a typology of cutting and packing problems. Eur J Oper Res 44(2):145–159. https://doi.org/10.1016/0377-2217(90)90350-K
Fanjul-Peyro L, Ruiz R (2011) Size-reduction heuristics for the unrelated parallel machines scheduling problem. Comput Oper Res 38(1):301–309. https://doi.org/10.1016/j.cor.2010.05.005
Gramani MCN, França PM (2006) The combined cutting stock and lot-sizing problem in industrial processes. Eur J Oper Res 174(1):509–521. https://doi.org/10.1016/j.ejor.2004.12.019
Kramer R, Subramanian A, Vidal T, Cabral LdAF (2015) A matheuristic approach for the pollution-routing problem. Eur J Oper Res 243(2):523–539. https://doi.org/10.1016/j.ejor.2014.12.009
Li S (1996) Multi-job cutting stock problem with due dates and release dates. J Oper Res Soc 47(4):490–510. https://doi.org/10.1057/jors.1996.56
Lin SW, Ying KC (2016) Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics. Omega 64:115–125. https://doi.org/10.1016/j.omega.2015.12.002
Martello S (1990) Knapsack problems: algorithms and computer implementations. Wiley-Interscience series in discrete mathematics and optimiza tion
Melega GM, de Araujo SA, Jans R (2018) Classification and literature review of integrated lot-sizing and cutting stock problems. Eur J Oper Res 271(1):1–19. https://doi.org/10.1016/j.ejor.2018.01.002
Melo MT, Nickel S, Saldanha-da Gama F (2014) An efficient heuristic approach for a multi-period logistics network redesign problem. TOP 22(1):80–108. https://doi.org/10.1007/s11750-011-0235-3
Miranda PL, Morabito R, Ferreira D (2018) Optimization model for a production, inventory, distribution and routing problem in small furniture companies. TOP 26(1):30–67. https://doi.org/10.1007/s11750-017-0448-1
Montgomery DC (2013) Design and analysis of experiments, 8th edn. Wiley, Hoboken
Nonås SL, Thorstenson A (2000) A combined cutting-stock and lot-sizing problem. Eur J Oper Res 120(2):327–342. https://doi.org/10.1016/S0377-2217(99)00160-5
Nonås SL, Thorstenson A (2008) Solving a combined cutting-stock and lot-sizing problem with a column generating procedure. Comput Oper Res 35(10):3371–3392. https://doi.org/10.1016/j.cor.2007.03.005
Ozer EA, Sarac T (2018) MIP models and a matheuristic algorithm for an identical parallel machine scheduling problem under multiple copies of shared resources constraints. TOP pp 1–31, https://doi.org/10.1007/s11750-018-00494-x
Poldi K, de Araujo S (2016) Mathematical models and a heuristic method for the multiperiod one-dimensional cutting stock problem. Ann Oper Res 238(1–2):497–520. https://doi.org/10.1007/s10479-015-2103-2
Prata BA, Pitombeira-Neto AR, Sales CJM (2015) An integer linear programming model for the multiperiod production planning of precast concrete beams. J Constr Eng Manag 141(10):04015029. https://doi.org/10.1061/(ASCE)CO.1943-7862.0000991
Reinertsen H, Vossen T (2010) The one-dimensional cutting stock problem with due dates. Eur J Oper Res 201(3):701–711. https://doi.org/10.1016/j.ejor.2009.03.042
Trkman P, Gradisar M (2007) One-dimensional cutting stock optimization in consecutive time periods. Eur J Oper Res 179(2):291–301. https://doi.org/10.1016/j.ejor.2006.03.027
Wäscher G, HauSSner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur J Oper Res 183(3):1109–1130. https://doi.org/10.1016/j.ejor.2005.12.047
Yanasse H (1997) On a pattern sequencing problem to minimize the maximum number of open stacks. Eur J Oper Res 100(3):454–463. https://doi.org/10.1016/S0377-2217(97)84107-0
Yanasse HH, Lamosa MJP (2007) An integrated cutting stock and sequencing problem. Eur J Oper Res 183(3):1353–1370. https://doi.org/10.1016/j.ejor.2005.09.054
Yuen B (1991) Heuristics for sequencing cutting patterns. Eur J Oper Res 25(2):183–190. https://doi.org/10.1016/0377-2217(91)90222-H
Acknowledgements
The authors would like to thank Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq; Grant No.: 422464/2016-3) for the financial support.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Pitombeira-Neto, A.R., Prata, B.d.A. A matheuristic algorithm for the one-dimensional cutting stock and scheduling problem with heterogeneous orders. TOP 28, 178–192 (2020). https://doi.org/10.1007/s11750-019-00531-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-019-00531-3