A COLUMN GENERATION TECHNIQUE WITH MULTIPLE SUB-PROBLEMS FOR 2-DIMENSIONAL CUTTING STOCK PROBLEM
Article Sidebar
Main Article Content
บทคัดย่อ
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.