เครื่องมือเพิ่มประสิทธิภาพการตัดวัสดุ 1 มิติ

การเพิ่มประสิทธิภาพการตัดวัสดุ 1 มิติทำงานอย่างไร

ปัญหาการตัดวัสดุหนึ่งมิติ (cutting stock problem) ถามว่าจะตัดชิ้นงานที่ต้องการจากวัสดุความยาวมาตรฐาน (เหล็กเส้น ท่อ โปรไฟล์ อะลูมิเนียมรีดขึ้นรูป) โดยใช้วัสดุให้น้อยที่สุดได้อย่างไร ปัญหานี้เป็น NP-hard เครื่องมือเชิงปฏิบัติจึงใช้ฮิวริสติกที่รวดเร็ว ซึ่งให้ผลใกล้ค่าเหมาะที่สุดมากสำหรับรายการสั่งตัดทั่วไปของโรงงาน

First Fit Decreasing (FFD) เรียงชิ้นงานทั้งหมดจากยาวสุดไปสั้นสุด แล้ววางแต่ละชิ้นลงในวัสดุท่อนแรกที่ยังมีที่ว่าง หากไม่มีท่อนใดพอจะเปิดท่อนใหม่ ส่วน Best Fit Decreasing (BFD) เรียงจากมากไปน้อยเช่นกัน แต่วางแต่ละชิ้นลงในท่อนที่จะเหลือพื้นที่น้อยที่สุดหลังวาง ซึ่งอาจจัดชุดที่พอดีกันได้แน่นกว่าเล็กน้อยในบางส่วนผสมของออเดอร์

การตัดแต่ละครั้งกินวัสดุเท่ากับความกว้างรอยเลื่อย เครื่องคำนวณนี้ใส่รอยเลื่อยระหว่างชิ้นงานที่ติดกันบนวัสดุท่อนเดียวกัน (ชิ้นงาน n ชิ้นต้องตัด n − 1 ครั้ง) เศษที่รายงานจึงแยกเศษปลายท่อนจริงออกจากการสูญเสียจากรอยเลื่อย สำหรับ FFD ทฤษฎีรับประกันว่าผลลัพธ์จะไม่เกิน 11/9 × ค่าเหมาะที่สุด + 6/9 ท่อน (Dósa, 2007) — ในทางปฏิบัติมักได้ค่าเหมาะที่สุดหรือเกินเพียงหนึ่งท่อน

ควรใช้เครื่องมือนี้เมื่อใด

• ตัดรายการสั่งตัดเหล็กเส้นเสริมคอนกรีต เหล็กโครงสร้าง ท่อ หรืออะลูมิเนียมโปรไฟล์จากวัสดุมาตรฐาน 6 m หรือ 12 m
• ประมาณจำนวนท่อนวัสดุที่ต้องซื้อสำหรับงานประกอบก่อนสั่งวัสดุ
• เปรียบเทียบเศษเหลือทิ้งระหว่างความยาววัสดุสองแบบที่ซัพพลายเออร์เสนอ เพื่อเลือกตัวเลือกที่ถูกกว่า
• สร้างใบลำดับการตัดสำหรับพนักงานเลื่อย พร้อมป้ายกำกับชิ้นงานในแต่ละท่อน
• วัดปริมาณการสูญเสียจากรอยเลื่อยแยกจากเศษปลายท่อน เมื่อต้องให้เหตุผลสนับสนุนการใช้ใบเลื่อยที่บางกว่า

ข้อผิดพลาดที่พบบ่อยที่ควรหลีกเลี่ยง

• ละเลยรอยเลื่อย — บนท่อน 6 m ที่ตัดเป็น 20 ชิ้น รอยเลื่อย 3 mm กินวัสดุ ~57 mm ซึ่งอาจดันชิ้นสุดท้ายไปอยู่ท่อนใหม่
• สลับหน่วยระหว่างความยาววัสดุตั้งต้นกับรายการชิ้นงาน (กรอกวัสดุเป็นเมตรแต่ชิ้นงานเป็นมิลลิเมตร)
• กรอกจำนวนชิ้นรวมของหลายชุดประกอบแทนการใช้คอลัมน์จำนวน ทำให้ตรวจสอบรายการสั่งตัดได้ยาก
• ถือว่าผลของฮิวริสติกเป็นค่าเหมาะที่สุดที่รับประกันได้สำหรับงบวัสดุที่วิกฤตด้านความปลอดภัย — สำหรับการผลิตอุตสาหกรรมขนาดใหญ่ วิธี LP แบบ column generation อาจประหยัดวัสดุได้อีกหลายท่อน
• ลืมว่าเศษที่ยังใช้ได้ (เศษปลายยาว) ถูกนับเป็นเศษเหลือทิ้งที่นี่ — หากคุณเก็บเศษไว้ใช้ซ้ำ ให้หักออกจากเศษที่รายงาน

วิธีตีความผลลัพธ์

• วัสดุที่ใช้คือตัวเลขหลัก — เปรียบเทียบกับขอบเขตล่าง ⌈ความยาวชิ้นงานรวม ÷ ความยาววัสดุ⌉ เพื่อประเมินว่าแผนการตัดแน่นเพียงใด
• อัตราการใช้ประโยชน์เกิน ~90% ถือว่าดีสำหรับรายการสั่งตัดแบบผสม เกิน 95% ถือว่ายอดเยี่ยมและมักหมายความว่าความยาวชิ้นงานเข้าคู่กับความยาววัสดุได้ดี
• เศษต่อรูปแบบแสดงว่าท่อนใดแบกเศษปลาย — ท่อนเดียวที่มีเศษส่วนใหญ่มักให้เศษปลายที่ยังใช้ประโยชน์ได้
• การสูญเสียจากรอยเลื่อยเพิ่มตามจำนวนชิ้น ไม่ใช่ความยาวชิ้น — ชิ้นสั้นจำนวนมากเสียวัสดุให้ใบเลื่อยเป็นสัดส่วนที่สูงกว่า
• หาก FFD และ BFD ให้จำนวนท่อนเท่ากัน แผนการตัดแทบจะเหมาะที่สุดแน่นอนสำหรับความยาววัสดุนั้น หากต่างกันให้เลือกแบบที่ดีกว่า

มาตรฐานและเอกสารอ้างอิงที่เกี่ยวข้อง

• Gilmore & Gomory (1961) — A Linear Programming Approach to the Cutting-Stock Problem (Operations Research 9:849-859) วิธีแก้แบบแม่นตรงที่เป็นรากฐาน
• Dósa (2007) — ขอบเขตกรณีเลวร้ายสุดแบบแน่นสำหรับ First Fit Decreasing: FFD(I) ≤ 11/9·OPT(I) + 6/9
• Johnson (1973) — Near-optimal bin packing algorithms (MIT) การวิเคราะห์คลาสสิกของกลุ่มฮิวริสติก FFD/BFD
• ความยาววัสดุเชิงพาณิชย์มักเป็นท่อนจากโรงรีด 6000 mm และ 12000 mm สำหรับเหล็กเส้นและเหล็กรูปพรรณโครงสร้าง ตรวจสอบรายการของซัพพลายเออร์ก่อนทำการเพิ่มประสิทธิภาพ

คำถามที่พบบ่อย

ควรเลือก FFD หรือ BFD?

ทั้งสองเรียงชิ้นงานจากยาวสุดก่อนเหมือนกัน ต่างกันเพียงวิธีเลือกท่อน: FFD เลือกท่อนแรกที่มีที่ว่าง ส่วน BFD เลือกท่อนที่พอดีที่สุด โดยปกติทั้งคู่ให้จำนวนท่อนเท่ากัน เมื่อต่างกันจะต่างเพียงหนึ่งท่อน รันทั้งสองแบบ (คลิกเดียว) แล้วเก็บแผนที่ดีกว่า

รอยเลื่อยถูกนำมาคิดอย่างไร?

รอยเลื่อยถูกบวกระหว่างชิ้นงานที่ติดกันบนวัสดุท่อนเดียวกัน — ชิ้นงาน n ชิ้นต้องตัด n − 1 ครั้ง เศษปลายท้ายท่อนไม่ต้องตัดเพิ่ม ตั้งค่ารอยเลื่อยตามความกว้างใบเลื่อยหรือหัวตัดจริงของคุณ (โดยทั่วไป 2-4 mm สำหรับเลื่อยตัดเย็น และ 1-2 mm สำหรับเลื่อยสายพาน)

ผลลัพธ์อาจแย่กว่าค่าเหมาะที่สุดจริงได้หรือไม่?

ได้ แต่ด้วยส่วนต่างเล็กน้อยที่พิสูจน์ได้: FFD ไม่มีวันใช้เกิน 11/9 ของจำนวนท่อนที่เหมาะที่สุดบวกค่าคงที่ สำหรับรายการสั่งตัดระดับโรงงานผลมักเหมาะที่สุดเกือบเสมอ ส่วนการผลิตระดับโรงรีดที่มีชิ้นงานหลายพันชิ้น ตัวแก้แบบแม่นตรงด้วย column generation อาจประหยัดวัสดุได้เพิ่มอีกในบางครั้ง