ONE-DIMENSIONAL CUTTING STOCK PROBLEM THAT MINIMIZES THE NUMBER OF DIFFERENT PATTERNS

  • Bib Paruhum Silalahi Department of Mathematics, Faculty of Mathematics and Natural Sciences, IPB University
  • Farida Hanum Department of Mathematics, Faculty of Mathematics and Natural Sciences, IPB University
  • Fajar Setyawan Department of Mathematics, Faculty of Mathematics and Natural Sciences, IPB University
  • Prapto Tri Supriyo Department of Mathematics, Faculty of Mathematics and Natural Sciences, IPB University
Keywords: Column Generation, Cutting Stock Problem, Different Pattern, Linear Programming, Setup Cost

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

Download data is not yet available.

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.

Published
2022-09-01
How to Cite
[1]
B. Silalahi, F. Hanum, F. Setyawan, and P. Supriyo, “ONE-DIMENSIONAL CUTTING STOCK PROBLEM THAT MINIMIZES THE NUMBER OF DIFFERENT PATTERNS”, BAREKENG: J. Math. & App., vol. 16, no. 3, pp. 805-814, Sep. 2022.