ONE-DIMENSIONAL CUTTING STOCK PROBLEM THAT MINIMIZES THE NUMBER OF DIFFERENT PATTERNS
Abstract
Cutting stock problem (CSP) is a problem of cutting an object into several smaller objects to fulfill the existing demand with a minimum unused object remaining. Besides minimizing the remaining of the object, sometimes there is another additional problem in CSP, namely minimizing the number of different cutting patterns. This happens because there is a setup cost for each pattern. This study shows a way to obtain a minimum number of different patterns in the cutting stock problem (CSP). An example problem is modeled in linear programming and then solved by a column generation algorithm using the Lingo 18.0 software.
Downloads
References
J. ben Amor Hatem and Valério de Carvalho, “Cutting Stock Problems,” in Column Generation, J. and S. M. M. Desaulniers Guy and Desrosiers, Ed. Boston, MA: Springer US, 2005, pp. 131–161. doi: 10.1007/0-387-25486-2_5.
N. Rodrigo, “One-Dimensional Cutting Stock Problem with Cartesian Coordinate Points,” International Journal of Systems Science and Applied Mathematics, vol. 2, no. 5, 2017, doi: 10.11648/j.ijssam.20170205.14.
H. Reinertsen and T. W. M. Vossen, “The one-dimensional cutting stock problem with due dates,” European Journal of Operational Research, vol. 201, no. 3, 2010, doi: 10.1016/j.ejor.2009.03.042.
S. Umetani, M. Yagiura, and T. Ibaraki, “One-dimensional cutting stock problem to minimize the number of different patterns,” European Journal of Operational Research, vol. 146, no. 2, 2003, doi: 10.1016/S0377-2217(02)00239-4.
F. Vanderbeck, “Exact algorithm for minimizing the number of setups in the one-dimensional cutting stock problem,” Operations Research, vol. 48, no. 6, 2000, doi: 10.1287/opre.48.6.915.12391.
Y. Cui, C. Zhong, and Y. Yao, “Pattern-set generation algorithm for the one-dimensional cutting stock problem with setup cost,” European Journal of Operational Research, vol. 243, no. 2, 2015, doi: 10.1016/j.ejor.2014.12.015.
G. Belov and G. Scheithauer, “Setup and open-stacks minimization in one-dimensional stock cutting,” INFORMS Journal on Computing, vol. 19, no. 1, 2007, doi: 10.1287/ijoc.1050.0132.
N. Ma, Y. Liu, and Z. Zhou, “Two heuristics for the capacitated multi-period cutting stock problem with pattern setup cost,” Computers and Operations Research, vol. 109, 2019, doi: 10.1016/j.cor.2019.05.013.
M. Martin, A. Moretti, M. Gomes-Ruggiero, and L. S. Neto, “Modification of Haessler’s sequential heuristic procedure for the one-dimensional cutting stock problem with setup cost,” Production, vol. 28, 2018, doi: 10.1590/0103-6513.20170105.
F. Clautiaux, R. Sadykov, F. Vanderbeck, and Q. Viaud, “Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers,” EURO Journal on Computational Optimization, vol. 7, no. 3, 2019, doi: 10.1007/s13675-019-00113-9.
D. Wang, F. Xiao, L. Zhou, and Z. Liang, “Two-dimensional skiving and cutting stock problem with setup cost based on column-and-row generation,” European Journal of Operational Research, vol. 286, no. 2, 2020, doi: 10.1016/j.ejor.2020.03.060.
H. H. Yanasse and M. S. Limeira, “A hybrid heuristic to reduce the number of different patterns in cutting stock problems,” Computers and Operations Research, vol. 33, no. 9, 2006, doi: 10.1016/j.cor.2005.02.026.
Y. Cui, L. Yang, Z. Zhao, T. Tang, and M. Yin, “Sequential grouping heuristic for the two-dimensional cutting stock problem with pattern reduction,” International Journal of Production Economics, vol. 144, no. 2, 2013, doi: 10.1016/j.ijpe.2013.03.011.
L. Pradenas, J. Garcés, V. Parada, and J. Ferland, “Genotype-phenotype heuristic approaches for a cutting stock problem with circular patterns,” Engineering Applications of Artificial Intelligence, vol. 26, no. 10, 2013, doi: 10.1016/j.engappai.2013.08.003.
Wayne L. Winston, Operations Research: Applications and Algorithms, Forth Edition. 2004.
J. Desrosiers and M. E. Lübbecke, “A primer in column generation,” in Column Generation, 2005. doi: 10.1007/0-387-25486-2_1.
K. Wibowo, “Analisa dan evaluasi: Akar penyebab dan biaya sisa material konstruksi proyek pembangunan kantor kelurahan, sekolah, dan pasar di Surakarta dan sekitarnya menggunakan metode root cause dan fault tree analysis,” 2017.
G. Belov and G. Scheithauer, “The number of setups (different patterns) in one-dimensional stock cutting,” MATH-NM-15-2003, Department of, 2003.
I. Griva, S. G. Nash, and A. Sofer, Linear and Nonlinear Optimization. Philadelphia: SIAM, 2009.
Copyright (c) 2022 Bib Paruhum Silalahi, Farida Hanum, Fajar Setyawan, Prapto Tri Supriyo
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors who publish with this Journal agree to the following terms:
- Author retain copyright and grant the journal right of first publication with the work simultaneously licensed under a creative commons attribution license that allow others to share the work within an acknowledgement of the work’s authorship and initial publication of this journal.
- Authors are able to enter into separate, additional contractual arrangement for the non-exclusive distribution of the journal’s published version of the work (e.g. acknowledgement of its initial publication in this journal).
- Authors are permitted and encouraged to post their work online (e.g. in institutional repositories or on their websites) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published works.
1.gif)
