A COLUMN GENERATION TECHNIQUE WITH MULTIPLE SUB-PROBLEMS FOR 2-DIMENSIONAL CUTTING STOCK PROBLEM
Article Sidebar
Main Article Content
Abstract
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 เปอร์เซ็นต์เมื่อเปรียบเทียบกับวิธีหาคำตอบพื้นฐาน
Downloads
Article Details
I and co-author(s) certify that articles of this proposal had not yet been published and is not in the process of publication in journals or other published sources. I and co-author accept the rules of the manuscript consideration. Both agree that the editors have the right to consider and make recommendations to the appropriate source. With this rights offering articles that have been published to Panyapiwat Institute of Management. If there is a claim of copyright infringement on the part of the text or graphics that appear in the article. I and co-author(s) agree on sole responsibility.
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.