Linear Integer Optimization Model for Two-Stage Guillotine Cutting Stock Problem Using Branch and Bound Method in the Garment Industry

Eman Lesmana; Julita Nahar; Annisa D. P

doi:10.47194/ijgor.v1i1.17

Authors

Eman Lesmana
eman.lesmana@unpad.ac.id
Julita Nahar
Annisa D. P

Keywords:

Two dimensional stock cutting problems, two-stage guillotine patterns, linear integer programming, branch and bound methods, graphical user interface.

Abstract

This paper discusses the Two-Stage Guillotine Cutting Stock Problem (2GCSP) in the garment industry, namely how to determine the two-stage guillotine pattern that is used to cut fabric stocks into several certain size t-shirt materials that are produced based on the demand for each size of the shirt. 2GCSP is modeled in the form of Linear Integer Optimization and finding solutions using the Branch and Bound method. In this paper also presented a Graphical User Interface with Maple software as an interactive tool to find the best fabric stock cutting patterns. The results show that the optimal solution can be determined by solving numerically using the Branch and Bound method and Maple optimization packages. The solution is shown with an illustration of the pattern and the amount of fabric cut based on the pattern.

References

Andrianova, A. A., Korepanova, A. A. & Halilova, I. F. (2016). One algorithm for branch and bound method for solvingconcave optimization problem. IOP Conf. Series: Materials Science and Engineering, 158, pp. 012005.

Chen, Q. L., Li, L. P., Cui, Y. D., Chen, Y. & Lu, X. Y. (2015). A Heuristic for the 3-staged 2D Cutting StockProblem with Usable Leftover. International Conference of Electrical, Automation and Mechanical Engineering, pp. 776-779.

Chinneck, J. W. (2015). Practical Optimization: a Gentle Introduction. (This version dated June 23, 2015 and available online atwww.sce.carleton.ca/faculty/chinneck/po.html)

Genova, K. & Guliashki, V. (2011). Linear Integer Programming Methods and Approaches â€“ A Survey. Cybernetics and Information Technologies, 11(1), pp. 3-25.

Jiao, H., Wang, F. & Chen, Y. (2014). An Effective Branch and Bound Algorithm for Minimax LinearFractional Programming. Journal of Applied Mathematics, 2014, 8 pages.

Kavun, S., Daradkeh, Y. I., Aldhaifallah, M. (2014). Method of the Integer Linear Programming. Mitteilungen Klosterneuburg, 64, pp. 1-13.

Mikolajkova, M., Saxen, H. & Pettersson, F. (2018). Mixed Integer Linear Programming Optimization of Gas Supply to aLocal Market. Ind. Eng. Chem. Res., 57, pp. 5951-5965.

Mrad, M., Meftahi, I. & Haouari, M. (2013). A branch-and-price algorithm for the two-stageguillotine cutting stock problem. Journal of the Operational Research Society, 64, pp. 629-637.

Qu, X., Yi, W., Wang, T., Wang, S., Xiao, L. & Liu, Z. (2017). Mixed-Integer Linear Programming Models forTeaching Assistant Assignment and Extensions. Scientific Programming, 2017, 7 pages.

Smirnova, S.& Voloshinov, V.(2018). On Domain Decomposition Strategies to Parallelize Branch-and-Bound Method for Global Optimization in Everest Distriburted Environment. Procedia Computer Science, 136, pp. 128-135.

Tian, B. & Posypkin, M. (2014). Efficient Implementationof Branch-and-Bound Methodon Desktop Grids. Computer Science, 15(3), pp. 239-252.

Wang, L., Ni, M., Gao, J., Shen, Q., Jia, Y. & Yao, C. (2019). The Loading Optimization: A Novel Integer LinearProgramming Model. Enterprise Information Systems. doi: 10.1080/17517575.2019.1631964

Widyastiti, M., Aman, A. & Bakhtiar, T. (2016). Nurses Scheduling by Considering the Qualificationusing Integer Linear Programming. Telkomnika, 14(3), pp. 933-940.

Wu, J. & Ge, X. (2012). Optimization Research of Generation Investment Based onLinear Programming Model. Physics Procedia, 24, pp. 1400-1405.

Zhao, X. & Cao, B. (2013). A Simplicial Branch and Bound Duality-Bounds Algorithm toLinear Multiplicative Programming. Journal of Applied Mathematics, 2013, 10 pages.