A method for demand-accurate one-dimensional cutting problems with pattern reduction

Haihua Xiao; Qiaokang Liang; Dan Zhang; Suhua Xiao; Gangzhuo Nie; Haihua Xiao; Qiaokang Liang; Dan Zhang; Suhua Xiao; Gangzhuo Nie

doi:10.3934/mbe.2023323

Mathematical Biosciences and Engineering

2023, Volume 20, Issue 4: 7453-7486. doi: 10.3934/mbe.2023323

Previous Article Next Article

Research article

A method for demand-accurate one-dimensional cutting problems with pattern reduction

1.
College of Electrical and Information Engineering, Hunan University, Changsha 410082, China
2.
National Engineering Laboratory for Robot Vision Perception and Control, Changsha 410082, China
3.
Department of Mechanical Engineering, York University, Toronto ONM3J1P3, Canada
4.
College of Electromechanical Engineering, Guangdong Polytechnic Normal University, Guangzhou 510635, China
5.
Aluminum Corporation of China, Beijing 100000, China

Academic Editor: Xiaodong Huang

Received: 27 October 2022 Revised: 19 January 2023 Accepted: 29 January 2023 Published: 15 February 2023

The main objective in the one-dimensional cutting stock problem (1D-CSP) is to minimize material costs. In practice, it is useful to focus on auxiliary objectives, one of which is to reduce the number of different cutting patterns. This paper discusses the classical integer IDCSP, where only one type of stock object is included. Meanwhile, the demands of various items must be precisely satisfied in the constraints. In other words, no overproduction or underproduction is allowed. Therefore, to solve this issue, a variable-to-constant method based on a new mathematical model is proposed. In addition, we integrate the approach with two other representative methods to demonstrate its effectiveness. Both benchmark instances and real instances are used in the experiments, and the results show that the methodology is effective in reducing patterns. In particular, in terms of the solutions to the real-life instances, the proposed approach presents a 31.93 to 37.6% pattern reduction compared to other similar methods (including commercial software).
- cutting,
- cutting stock,
- cutting pattern,
- column generation,
- optimization algorithms
Citation: Haihua Xiao, Qiaokang Liang, Dan Zhang, Suhua Xiao, Gangzhuo Nie. A method for demand-accurate one-dimensional cutting problems with pattern reduction[J]. Mathematical Biosciences and Engineering, 2023, 20(4): 7453-7486. doi: 10.3934/mbe.2023323

Related Papers:

Abstract

The main objective in the one-dimensional cutting stock problem (1D-CSP) is to minimize material costs. In practice, it is useful to focus on auxiliary objectives, one of which is to reduce the number of different cutting patterns. This paper discusses the classical integer IDCSP, where only one type of stock object is included. Meanwhile, the demands of various items must be precisely satisfied in the constraints. In other words, no overproduction or underproduction is allowed. Therefore, to solve this issue, a variable-to-constant method based on a new mathematical model is proposed. In addition, we integrate the approach with two other representative methods to demonstrate its effectiveness. Both benchmark instances and real instances are used in the experiments, and the results show that the methodology is effective in reducing patterns. In particular, in terms of the solutions to the real-life instances, the proposed approach presents a 31.93 to 37.6% pattern reduction compared to other similar methods (including commercial software).

References

[1]	P. Gilmore, R. E. Gomory, A linear programming approach to the cutting-stock problem, Comput. Oper. Res., 9 (1961), 849–859. http://doi.org/10.1287/opre.9.6.849 doi: 10.1287/opre.9.6.849
[2]	H. H. Yanasse, M. S. Limeira, A hybrid heuristic to reduce the number of different patterns in cutting stock problems, Comput. Oper. Res., 33 (2006), 2744–2756. https://doi.org/10.1016/j.cor.2005.02.026 doi: 10.1016/j.cor.2005.02.026
[3]	A. C. Cherri, M. N. Arenales, H. H. Yanasse, K. C. Poldi, A. C. G. Vianna, The one-dimensional cutting stock problem with usable leftovers-A survey, Eur. J. Oper. Res., 236 (2014), 395–402. https://doi.org/10.1016/j.ejor.2013.11.026 doi: 10.1016/j.ejor.2013.11.026
[4]	Y. Cui, C. Zhong, Y. Yao, Pattern-set generation algorithm for the one-dimensional cutting stock problem with setup cost, Eur. J. Oper. Res., 243 (2015), 540–546. https://doi.org/10.1016/j.ejor.2014.12.015 doi: 10.1016/j.ejor.2014.12.015
[5]	M. Martin, H. H. Yanasse, L. L. Salles-Neto, Pattern-based ILP models for the one-dimensional cutting stock problem with setup cost, J. Comb. Optim., 44 (2022), 557–582. https://doi.org/10.1007/s10878-022-00848-z doi: 10.1007/s10878-022-00848-z
[6]	Y. Cui, Z. Liu, C-Sets-based sequential heuristic procedure for the one dimensional cutting stock problem with pattern reduction, Optim. Methods Software, 26 (2011), 55–167. https://doi.org/10.1080/10556780903420531 doi: 10.1080/10556780903420531
[7]	H. H. Yanasse, K. C. Poldi, G. R. L. Cerqueira, Modified KOMBI to reduce the different patterns in cutting stock problems, International Federation of Operational Research Societies Melbourne, Australia, 2011.
[8]	A. Mobasher, A. Ekici, Solution approaches for the cutting stock problem with setup cost, Comput. Oper. Res., 40 (2013), 225–235. https://doi.org/10.1016/j.cor.2012.06 doi: 10.1016/j.cor.2012.06
[9]	L.N. López de Lacalle, Improving the high-speed finishing of forming tools for advanced high-strength steels (AHSS), Int. J. Adv. Manuf. Technol., 29 (2006), 49–63. https://doi.org/10.1016/j.cor.2012.06.007 doi: 10.1016/j.cor.2012.06.007
[10]	A. I. Hinxman, The trim-loss and assortment problems: a survey, Eur. J. Oper. Res., 5 (2007), 8–18. https://doi.org/10.1016/0377-2217(80)90068-5 doi: 10.1016/0377-2217(80)90068-5
[11]	P. Ongkunaruk, Asymptotic worst-case analyses for the open bin packing problem, Faculty of the Virginia Polytechnic Institute, 2005.
[12]	A. C. Cherri, M. N. Arenales, H. H. Yanasse, The one-dimensional cutting stock problem with usable leftover: a heuristic approach, Eur. J. Oper. Res., 6 (2009), 897–908. https://doi.org/10.1016/j.ejor.2008.04.039 doi: 10.1016/j.ejor.2008.04.039
[13]	K. C. Poldi, M. N. Arenales, Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths, Comput. Oper. Res., 36 (2009), 2074–2081. https://doi.org/10.1016/j.cor.2008.07.001 doi: 10.1016/j.cor.2008.07.001
[14]	Y. Cui, Y. P. Cui, Z. Zhao, Pattern-set generation algorithm for the one one-dimensional multiple stock sizes cutting stock problem, Eng. Optim., 9 (2015), 1289–1301. https://doi.org/10.1080/0305215X.2014.969726 doi: 10.1080/0305215X.2014.969726
[15]	G. Cerqueira, S. S. Aguiar, M. Marques, Modified greedy heuristic for the one-dimensional cutting stock problem. J. Comb. Optim., 42 (2021), 657–674. https://doi.org/10.1007/s10878-021-00695-4 doi: 10.1007/s10878-021-00695-4
[16]	R. W. Haessler, Controlling cutting pattern changes in one-dimensional trim Problems, Comput. Oper. Res., 23 (1975), 483–493. https://doi.org/10.2307/169698 doi: 10.2307/169698
[17]	S. Umetani, M. Yagiura, T. Ibaraki, One-dimensional cutting stock problem to minimize the number of different patterns, Eur. J. Oper. Res., 146 (2003), 388–402. https://doi.org/10.1016/S0377-2217(02)00239-4 doi: 10.1016/S0377-2217(02)00239-4
[18]	J. Lee, In situ column generation for a cutting-stock problem, Comput. Oper. Res., 34 (2007), 2345–2358. https://doi.org/10.1016/j.cor.2005.09.007 doi: 10.1016/j.cor.2005.09.007
[19]	R. R. Golfeto, A. C. Moretti, L. L. S. Neto, A genetic symbiotic algorithm applied to the cutting stock problem with multiple objectives, Adv. Model. Optim., 11 (2009), 473–501.
[20]	S. A. Araujo, K. C. Poldi, J. Smith, A genetic algorithm for the one-dimensional cutting stock problem with setups, Pesqui. Oper., 34 (2014), 165–187. https://doi.org/10.1590/0101-7438.2014.034.02.0165 doi: 10.1590/0101-7438.2014.034.02.0165
[21]	A. Mobasher, A. Ekici, Olution approaches for the cutting stock problem with setup cost, Comput. Oper. Res., 40 (2013), 225–235.https://doi.org/10.1016/j.cor.201206.007 doi: 10.1016/j.cor.201206.007
[22]	M. Martin, A. Moretti, M. Gomes-Ruggiero, L. S. Neto, Modifification of Haessler's sequential heuristic procedure for the one-dimensional cutting stock problem with setup cost, Production, 28 (2018), e20170105. https://doi.org/10.1590/0103-6513.20170105 doi: 10.1590/0103-6513.20170105
[23]	C. McDiarmid, Pattern minimisation in cutting stock problems, Discrete Appl. Math., 98 (1999), 121–130. https://doi.org/10.1016/S0166-218X(99)00112-2 doi: 10.1016/S0166-218X(99)00112-2
[24]	F. Vanderbeck, Exact algorithm for minimizing the number of setups in the one-dimensional cutting stock problem, Oper. Res., 48 (2000), 915–926. https://doi.org/10.2307/222998 doi: 10.2307/222998
[25]	G. Belov, G. Scheithauer, The number of setups (different patterns) in one-dimensional stock cutting, Preprint MATH-NM-15-2003, Department of Mathematics, Dresden University of Technology, 2003
[26]	C. Alves, J. M. V. De Carvalho, A branch-and-price-and-cut algorithm for the pattern minimization problem, RAIRO Oper. Res., 42 (2008), 435–453. https://doi.org/10.1051/ro:2008027 doi: 10.1051/ro:2008027
[27]	C. Alves, R. Macedo, J. V. D. Carvalho, New lower bounds based on column generation and constraint programming for the pattern minimization problem, Comput. Oper. Res., 36 (2009), 2944–2954. https://doi.org/10.1016/j.cor.2009.01.008 doi: 10.1016/j.cor.2009.01.008
[28]	A. Aloisio, C. Arbib, F. Marinelli, On LP relaxations for the pattern minimization problem, Networks, 57 (2011), 247–253. https://doi.org/10.1002/net.20422 doi: 10.1002/net.20422
[29]	G. Wascher, T. Gau, Heuristics for the integer one-dimensional cutting stock problem: a computational study, Operations-Research-Spektrum, 18 (1996), 131–144. https://doi.org/10.1007/BF01539705 doi: 10.1007/BF01539705
[30]	M. Delorme, M. Iori, Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems, INFORMS J. Comput., 32 (2020), 101–119. https://doi.org/10.1287/ijoc.2018.0880 doi: 10.1287/ijoc.2018.0880
[31]	H. Foerster, G. Wäscher, Pattern reduction in one-dimensional cutting stock problems, Int. J. Prod. Res., 38 (2000), 1657–1676. https://doi.org/10.1080/002075400188780 doi: 10.1080/002075400188780
[32]	T. Gau, G. Wäscher, CUTGEN1: A problem generator for the one-dimensional cutting stock problem, Eur. J. Oper. Res., 84 (1995), 572–579. https://doi.org/10.1016/0377-2217(95)00023-J doi: 10.1016/0377-2217(95)00023-J

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)