การจัดตารางงาน Job-Shop (GA)

การจัดตารางงาน Job-Shop คืออะไร? GA แก้อย่างไร?

กำหนดการดำเนินงานของหลายงานให้เครื่องจักรเพื่อลด makespan หรือความล่าช้า แต่ละงานมีลำดับการดำเนินงานบนเครื่องจักรต่างๆ

JSSP เป็น NP-hard GA พัฒนาประชากรตารางงานผู้สมัคร POX crossover รักษาลำดับงาน swap mutation สลับตำแหน่ง

JSSP สำคัญในการผลิต ลด makespan 10-15% เพิ่มกำลังผลิตโดยตรงโดยไม่ต้องลงทุน

Formula: Makespan = max(เวลาเสร็จทั้งหมด) ความล่าช้า = Σ max(0, เสร็จ_j − กำหนด_j) GA: เริ่มต้น → ประเมิน → เลือก → POX → กลายพันธุ์ → ทำซ้ำ

ตัวอย่างการคำนวณ

3 งาน 3 เครื่อง งาน 1: M1(3)→M2(2)→M3(4) Makespan ดีที่สุด = 12 GA (ประชากร 100, 200 รุ่น) มักพบค่านี้หรือภายใน 5%

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

• ผู้วางแผนการผลิตจัดตารางงานหลายรายการข้ามเครื่องจักรที่ใช้ร่วมกัน
• วิศวกรการผลิตประเมินผลกระทบของเครื่องจักรใหม่
• ผู้จัดตารางกำหนดลำดับความสำคัญของงาน
• นักวิจัยปฏิบัติการเปรียบเทียบ GA กับวิธีการปัจจุบัน

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

• ขนาดประชากรเล็กเกินไปสำหรับปัญหาซับซ้อน
• จำนวนรุ่นน้อยเกินไป
• ไม่สนใจเวลาปล่อยและกำหนดส่ง
• ไม่รัน GA หลายครั้ง

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

• ความล่าช้ารวมเป็นศูนย์ ทุกงานเสร็จก่อนกำหนด
• Makespan ใกล้ผลรวมเวลาประมวลผลบนเครื่องคอขวด
• แผนภูมิ Gantt เผยเวลาว่างบนเครื่องจักร

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

• Garey, Johnson & Sethi (1976) — พิสูจน์ความเป็น NP-hard ของการลด makespan ในแบบ job-shop
• Makespan (C_max) และความล่าช้ารวม — ฟังก์ชันวัตถุประสงค์มาตรฐานในการจัดตารางการผลิต
• อัลกอริทึมเชิงพันธุกรรม (Holland, 1975) — กลุ่มเมตาฮิวริสติกที่นำมาใช้ที่นี่เพื่อค้นหาปริภูมิของตารางเวลา

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

ตั้งค่า GA อย่างไรเพื่อผลลัพธ์ที่ดี?

ประชากร 50-200 อัตรากลายพันธุ์ 0.05-0.15, 200-500 รุ่น ปัญหา 10+ งานใช้ประชากร ≥100, รุ่น ≥300

การเพิ่มประสิทธิภาพ makespan กับความล่าช้าต่างกันอย่างไร?

Makespan เน้นเสร็จเร็วที่สุด ดีสำหรับกำลังผลิต ความล่าช้าเน้นตรงกำหนด อาจขัดแย้งกัน การเพิ่มประสิทธิภาพหลายเป้าหมายสร้างสมดุล