Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
คอลัมน์เจเนเรชันที่มีฮิวริสติกสำหรับปัญหาการตัดวัตถุแบบกิโยตีนสองมิติที่มีเศษที่ใช้ได้
Year (A.D.)
2018
Document Type
Thesis
First Advisor
Boonyarit Intiyot
Second Advisor
Chawalit Jeenanunta
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Department (if any)
Department of Mathematics and Computer Science (ภาควิชาคณิตศาสตร์และวิทยาการคอมพิวเตอร์)
Degree Name
Doctor of Philosophy
Degree Level
Doctoral Degree
Degree Discipline
Applied Mathematics and Computational Science
DOI
10.58837/CHULA.THE.2018.1588
Abstract
The two-dimensional cutting stock problem with usable leftover (2DCSPUL) aims to minimize the waste from cutting in two aspects. The first aspect focuses on the suitable cutting patterns that provide the minimum waste while satisfying a requirement. The second aspect is to utilize the waste in the cutting process by turning the waste with sufficient size into a raw material or an item for the next cutting period. In this dissertation, the common two-stage guillotine cutting pattern which is found in many large industries is considered in this problem. Two definitions of fixed size usable leftover are introduced. A column generation (CG) technique is applied in an attempt to find a solution where the sub-problem deals with two-dimensional knapsack problem (2DKP). Moreover, two heuristic procedures with column generation integrated, namely the simple heuristic and the truncated branch-and-price, are proposed to reduce the complexity of finding a good integer solution. Benchmark and real-world instances are used to test the performance of the algorithms as well as an effect of usable leftover. The computational results illustrate good performance of the algorithms in terms of 1) solution quality represented by the gap from the lower bound and 2) the computational time that are suitable for real industrial applications.
Other Abstract (Other language abstract of ETD)
ปัญหาการตัดในสองมิติที่มีเศษที่ใช้ได้มีวัตถุประสงค์เพื่อลดเศษที่เกิดจากการตัดแผ่นวัตถุให้มีค่าน้อยที่สุดในสองประเด็น ในประเด็นแรกจะพิจารณารูปแบบการตัดที่เหมาะสมที่ทำให้ได้ผลผลิตตามความต้องการและมีเศษที่เกิดขึ้นน้อยที่สุด สำหรับประเด็นที่สองจะเป็นการใช้ประโยชน์จากเศษที่เกิดขึ้นจากการตัด โดยเปลี่ยนเศษที่มีขนาดเพียงพอไปเป็นแผ่นวัตถุดิบหรือผลผลิตสำหรับการตัดในคาบถัดไป ในดุษฎีนิพนธ์นี้คำนึงถึงรูปแบบการตัดที่สอดคล้องกับการตัดในลักษณะกีโยตีนแบบสองขั้นตอน ซึ่งสามารถพบได้ทั่วไปในหลายอุตสาหกรรมใหญ่ และมีการนำเสนอนิยามของเศษที่ใช้ได้ที่มีการกำหนดขนาดอย่างแน่นอน เทคนิคคอลัมน์เจเนเรชันถูกนำมาใช้เพื่อหาคำตอบสำหรับปัญหานี้ซึ่งมีปัญหาย่อยสอดคล้องกับปัญหาถุงเป้ในสองมิติ นอกจากนี้มีการนำเสนอสองวิธีการทางฮิวริสติกซึ่งรวมกับเทคนิคคอลัมน์เจเนเรชัน ได้แก่ วิธีฮิวริสติกอย่างง่ายและวิธีแตกกิ่งและพิจารณาค่าตัวแปรแบบตัดปลายเพื่อลดความซับซ้อนในขั้นตอนการหาคำตอบที่เป็นจำนวนเต็ม ชุดข้อมูลมาตรฐานและชุดข้อมูลจริงถูกนำมาใช้เพื่อทดสอบประสิทธิภาพของวิธีการที่นำเสนอและรวมไปถึงผลกระทบจากการพิจารณาเศษที่ใช้ได้ ผลการวิจัยเชิงคำนวณแสดงถึงประสิทธิภาพที่ดีในเชิงของ 1) คุณภาพของคำตอบโดยพิจารณาจากระยะห่างของคำตอบจากขอบเขตล่าง และ2) เวลาในการคำนวณที่เหมาะสมที่จะนำไปใช้ในอุตสาหกรรมจริง
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Sumetthapiwat, Supphakorn, "Column generation with heuristic for two-dimensional guillotine cutting stock problem with usable leftover" (2018). Chulalongkorn University Theses and Dissertations (Chula ETD). 10772.
https://digital.car.chula.ac.th/chulaetd/10772
