Column Generation Model in Capacitated Multi-Periods Cutting Stock Problem with Pattern Set-Up Cost
Article Sidebar
Keywords:
-
Cutting Stock Problem, Pattern Generation, Gilmore-Gomory, Column Generation
Abstract
Cutting Stock Problem (CSP) determines the cutting of stocks with standard length and width to meet the item’s demand. The optimal cutting pattern will minimize the usage of stocks and trim loss. This research implemented the pattern generation algorithm to form the Gilmore-Gomory and Column Generation model in two-dimensional CSP. The CSP in this research had three periods of cutting with different capacities in each period. The Column Generation model added the pattern set-up cost as the constraint. The Gilmore-Gomory model ensured that the first stage’s strips were used in the second stage and met the item’s demand. Based on the Column Generation model’s solution, the 1st period used the 2nd, 4th, and 5th patterns, the 2nd period used 4th and 5th patterns, and the 3rd period did not use any patterns. The first and second periods fulfilled all of the demands.
References
Andrade, R., Birgin, E. G., & Morabito, R. (2016). Two-stage two-dimensional guillotine cutting stock problems with usable leftover. International Transactions in Operational Research, 23(1–2), 121–145. https://doi.org/10.1111/itor.12077
Arbib, C., Marinelli, F., & Ventura, P. (2016). One-dimensional cutting stock with a limited number of open stacks: Bounds and solutions from a new integer linear programming model. International Transactions in Operational Research, 23(1–2), 47–63. https://doi.org/10.1111/itor.12134
Bangun, P. B. J., Octarina, S., Sepriliani, S. P., Hanum, L., & Cahyono, E. S. (2020) 3-Phase matheuristic model in two-dimensional cutting stock problem of triangular shape items Science and Technology Indonesia, 5 (1) 1–5. https://doi.org/10.26554/sti.2020.5.1.23-27
Brandão, J. S., Coelho, A. M., & Carmo, J. F. V. (2012). Study of Different Setup Costs in SingleGA to Solve a One-Dimensional Cutting Stock Problem. GSTF Journal on Computing, 2(1), 1–6. https://doi.org/10.5176_2010-2283_2.1.118
Etebari, F. (2019). A column generation algorithm for the choice-based congested location-pricing problem. Computers and Industrial Engineering, 130 (March 2018), 687–698. https://doi.org/10.1016/j.cie.2019.03.023
Garraffa, M., Salassa, F., Vancroonenburg, W., Vanden Berghe, G., & Wauters, T. (2016). The one-dimensional cutting stock problem with sequence-dependent cut losses. International Transactions in Operational Research, 23(1–2), 5–24. https://doi.org/10.1111/itor.12095
Lin, D. Y., & Hsu, C. L. (2016). A column generation algorithm for the bus driver scheduling problem. Journal of Advanced Transportation, 50(8), 1598–1615. https://doi.org/10.1002/atr.1417
Ma, N., Liu, Y., & Zhou, Z. (2019). Two heuristics for the capacitated multi-period cutting stock problem with pattern setup cost. Computers and Operations Research, 109, 218–229. https://doi.org/10.1016/j.cor.2019.05.013
Ma, N., Liu, Y., Zhou, Z., & Chu, C. (2018). Combined cutting stock and lot-sizing problem with pattern setup. Computers and Operations Research, 95, 44–55. https://doi.org/10.1016/j.cor.2018.02.016
Octarina, S., Ananda, V., & Yuliza, E. (2019). Gilmore and gomory model on two dimensional multiple stock size cutting stock problem. Journal of Physics: Conference Series, 1282(1). https://doi.org/10.1088/1742-6596/1282/1/012015
Octarina, S., Janna, M., Cahyono, E. S., Bangun, P. B. J., & Hanum, L. (2020). The modified branch and bound algorithm and dotted board model for triangular shape items. Journal of Physics: Conference Series, 1480(1). https://doi.org/10.1088/1742-6596/1480/1/012065
Octarina, S., Radiana, M., & Bangun, P. B. J. (2018). Implementation of pattern generation algorithm in forming Gilmore and Gomory model for two dimensional cutting stock problem. IOP Conference Series: Materials Science and Engineering, 300(1). https://doi.org/10.1088/1757-899X/300/1/012021
Octarina, S., Ananda, V., & Yuliza, E. (2019). Gilmore and gomory model on two dimensional multiple stock size cutting stock problem. Journal of Physics: Conference Series, 1282(1). https://doi.org/10.1088/1742-6596/1282/1/012015
Octarina, S., Bangun, P. B. J., & Hutapea, S. (2017). The Application to Find Cutting Patterns in Two Dimensional Cutting Stock Problem. 1–5.
Octarina, S., Radiana, M., & Bangun, P. B. J. (2018). Implementation of pattern generation algorithm in forming Gilmore and Gomory model for two dimensional cutting stock problem. IOP Conference Series: Materials Science and Engineering, 300(1). https://doi.org/10.1088/1757-899X/300/1/012021
Rodrigo, N. (2017). One-Dimensional Cutting Stock Problem with Cartesian Coordinate Points. International Journal of Systems Science and Applied Mathematics, 2(5), 99. https://doi.org/10.11648/j.ijssam.20170205.14
Rodrigo, W. (2013). A Method for Two-Dimensional Cutting Stock Problem with Triangular Shape Items. British Journal of Mathematics & Computer Science, 3(4), 750–771. https://doi.org/10.9734/bjmcs/2013/5165
Rodrigo, W. N. P., Daundasekera, W., & Perera, A. A. I. (2012). Pattern Generation for Two-Dimensional Cutting Stock Problem with Location. Indian Journal of Mathematics Trends and Technology, 3(2), 354–368. http://core.kmi.open.ac.uk/download/pdf/5837130.pdf
Song, X., & Bennell, J. A. (2014). Column generation and sequential heuristic procedure for solving an irregular shape cutting stock problem. Journal of the Operational Research Society, 65(7), 1037–1052. https://doi.org/10.1057/jors.2013.44
Arbib, C., Marinelli, F., & Ventura, P. (2016). One-dimensional cutting stock with a limited number of open stacks: Bounds and solutions from a new integer linear programming model. International Transactions in Operational Research, 23(1–2), 47–63. https://doi.org/10.1111/itor.12134
Bangun, P. B. J., Octarina, S., Sepriliani, S. P., Hanum, L., & Cahyono, E. S. (2020) 3-Phase matheuristic model in two-dimensional cutting stock problem of triangular shape items Science and Technology Indonesia, 5 (1) 1–5. https://doi.org/10.26554/sti.2020.5.1.23-27
Brandão, J. S., Coelho, A. M., & Carmo, J. F. V. (2012). Study of Different Setup Costs in SingleGA to Solve a One-Dimensional Cutting Stock Problem. GSTF Journal on Computing, 2(1), 1–6. https://doi.org/10.5176_2010-2283_2.1.118
Etebari, F. (2019). A column generation algorithm for the choice-based congested location-pricing problem. Computers and Industrial Engineering, 130 (March 2018), 687–698. https://doi.org/10.1016/j.cie.2019.03.023
Garraffa, M., Salassa, F., Vancroonenburg, W., Vanden Berghe, G., & Wauters, T. (2016). The one-dimensional cutting stock problem with sequence-dependent cut losses. International Transactions in Operational Research, 23(1–2), 5–24. https://doi.org/10.1111/itor.12095
Lin, D. Y., & Hsu, C. L. (2016). A column generation algorithm for the bus driver scheduling problem. Journal of Advanced Transportation, 50(8), 1598–1615. https://doi.org/10.1002/atr.1417
Ma, N., Liu, Y., & Zhou, Z. (2019). Two heuristics for the capacitated multi-period cutting stock problem with pattern setup cost. Computers and Operations Research, 109, 218–229. https://doi.org/10.1016/j.cor.2019.05.013
Ma, N., Liu, Y., Zhou, Z., & Chu, C. (2018). Combined cutting stock and lot-sizing problem with pattern setup. Computers and Operations Research, 95, 44–55. https://doi.org/10.1016/j.cor.2018.02.016
Octarina, S., Ananda, V., & Yuliza, E. (2019). Gilmore and gomory model on two dimensional multiple stock size cutting stock problem. Journal of Physics: Conference Series, 1282(1). https://doi.org/10.1088/1742-6596/1282/1/012015
Octarina, S., Janna, M., Cahyono, E. S., Bangun, P. B. J., & Hanum, L. (2020). The modified branch and bound algorithm and dotted board model for triangular shape items. Journal of Physics: Conference Series, 1480(1). https://doi.org/10.1088/1742-6596/1480/1/012065
Octarina, S., Radiana, M., & Bangun, P. B. J. (2018). Implementation of pattern generation algorithm in forming Gilmore and Gomory model for two dimensional cutting stock problem. IOP Conference Series: Materials Science and Engineering, 300(1). https://doi.org/10.1088/1757-899X/300/1/012021
Octarina, S., Ananda, V., & Yuliza, E. (2019). Gilmore and gomory model on two dimensional multiple stock size cutting stock problem. Journal of Physics: Conference Series, 1282(1). https://doi.org/10.1088/1742-6596/1282/1/012015
Octarina, S., Bangun, P. B. J., & Hutapea, S. (2017). The Application to Find Cutting Patterns in Two Dimensional Cutting Stock Problem. 1–5.
Octarina, S., Radiana, M., & Bangun, P. B. J. (2018). Implementation of pattern generation algorithm in forming Gilmore and Gomory model for two dimensional cutting stock problem. IOP Conference Series: Materials Science and Engineering, 300(1). https://doi.org/10.1088/1757-899X/300/1/012021
Rodrigo, N. (2017). One-Dimensional Cutting Stock Problem with Cartesian Coordinate Points. International Journal of Systems Science and Applied Mathematics, 2(5), 99. https://doi.org/10.11648/j.ijssam.20170205.14
Rodrigo, W. (2013). A Method for Two-Dimensional Cutting Stock Problem with Triangular Shape Items. British Journal of Mathematics & Computer Science, 3(4), 750–771. https://doi.org/10.9734/bjmcs/2013/5165
Rodrigo, W. N. P., Daundasekera, W., & Perera, A. A. I. (2012). Pattern Generation for Two-Dimensional Cutting Stock Problem with Location. Indian Journal of Mathematics Trends and Technology, 3(2), 354–368. http://core.kmi.open.ac.uk/download/pdf/5837130.pdf
Song, X., & Bennell, J. A. (2014). Column generation and sequential heuristic procedure for solving an irregular shape cutting stock problem. Journal of the Operational Research Society, 65(7), 1037–1052. https://doi.org/10.1057/jors.2013.44
Authors
Bangun, P. B. J., Octarina, S., Hanum, L., Sawitri, R., & Cahyono, E. S. (2021). Column Generation Model in Capacitated Multi-Periods Cutting Stock Problem with Pattern Set-Up Cost. Science and Technology Indonesia, 6(1), 8–13. https://doi.org/10.26554/sti.2021.6.1.8-13
Copyright and license info is not available