A COLUMN GENERATION TECHNIQUE WITH MULTIPLE SUB-PROBLEMS FOR 2-DIMENSIONAL CUTTING STOCK PROBLEM

Main Article Content

Supphakorn Sumetthapiwat
Boonyarit Intiyot
Chawalit Jeenanunta

บทคัดย่อ

          In this paper, we discuss two-dimensional cutting stock problems (2DCSP) where the rectangular panels of difference sizes must be cut from standard multiple-size rolls. Moreover, the panels have to be obtained through two-stage guillotine cuts. The objective is to minimize the number of used rolls (or the area of waste). A new method based on column generation technique with multiple sub-problems is introduced to solve the problem. Various types and numbers of sub-problems are tested using real world data instances from electronic board industry. The computational results show the impact of solutions from difference sets and on average yield approximately 28 percent reduction of the waste area comparing with a basic method.

 

          ในบทความนี้ได้นำเสนอปัญหาการตัดแผ่นวัตถุในสองมิติเมื่อแผ่นวัตถุสี่เหลี่ยมเล็กขนาดต่างๆ ได้มาจากการตัดแผ่นวัตถุดิบที่มีขนาดสี่เหลี่ยมมาตรฐานที่มีหลากหลายขนาด นอกจากนี้การตัดแผ่นวัตถุดิบสี่เหลี่ยมมาตรฐานจะต้องตัดในลักษณะของการตัดแบบกิโยตีน 2 ขั้น โดยมีจุดมุ่งหมายคือ การใช้แผ่นวัตถุดิบสี่เหลี่ยมมาตรฐานจำนวนน้อยที่สุด หรือทำให้เหลือเศษจากการตัดน้อยที่สุด งานวิจัยนี้ได้นำเสนอวิธีใหม่ในการหาคำตอบซึ่งมีพื้นฐานมาจากเทคนิคคอลัมน์เจเนเรชันที่ประกอบไปด้วยหลายปัญหาย่อย โดยทำการทดสอบกับข้อมูลจริงจากอุตสาหกรรมผลิตแผงวงจรอิเล็กทรอนิกส์ ผลจากการทดลองพบว่า ชุดคำตอบเริ่มต้นที่แตกต่างกันมีผลกระทบกับคุณภาพของคำตอบ นอกจากนี้คำตอบที่ได้ส่งผลให้ลดปริมาณเศษจากการตัดโดยเฉลี่ย 28 เปอร์เซ็นต์เมื่อเปรียบเทียบกับวิธีหาคำตอบพื้นฐาน

Article Details

บท
บทความวิจัย

References

Alvarez-Valdes, R., Parajon, A. & Tamarit, M. J. (2002). A computational study of LP-based heuristic algorithms for two-dimensional guillotine cutting stock problems. OR Spectrum, 24(2), 179-192.

Cintra, G. F., Miyazawa, F. K., Wakabayashi, Y. & Xavier, E. C. (2008a). Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. European Journal of Operational Research, 191(1), 61-85.

Furini, F. & Malaguti, E. (2013). Models for the two-dimensional two-stage cutting stock problem with multiple stock size. Computers & Operations Research, 40(8), 1953-1962.

Furini, F., Malaguti, E., Medina Durán, R., Persiani, A. & Toth, P. (2012). A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size. European Journal of Operational Research, 218(1), 251-260.

Lodi, A. & Monaci, M. (2003). Integer linear programming models for 2-staged two-dimensional Knapsack problems. Mathematical Programming, 94(2-3), 257-278.

Riehme, J., Scheithauer, G. & Terno, J. (1996). The solution of two-stage guillotine cutting stock problems having extremely varying order demands. European Journal of Operational Research, 91(3), 543-552.

Skogestad, S., Harjunkoski, I., Pörn, R., Westerlund, T. & Skrifvars, H. (1997). Supplement to Computers and Chemical Engineering Different strategies for solving bilinear integer non-linear programming problems with convex transformations. Computers & Chemical Engineering, 21, S487-S492.

Yanasse, H. H. & Morabito, R. (2008b). A note on linear models for two-group and three-group two-dimensional guillotine cutting problems. International Journal of Production Research, 46(21), 6189-6206.