ตัวแก้ปัญหาการมอบหมาย

ปัญหาการมอบหมายคืออะไร?

ปัญหาการมอบหมายเป็นปัญหาการเพิ่มประสิทธิภาพเชิงผสม: กำหนด n ตัวแทนและ n งาน หาการมอบหมายแบบหนึ่งต่อหนึ่งที่ลดต้นทุนรวมให้น้อยที่สุด

อัลกอริทึมฮังการี (Kuhn-Munkres 1955) แก้ปัญหาใน O(n³) ลดเมทริกซ์ต้นทุนซ้ำๆ โดยการลบแถวและคอลัมน์ จากนั้นหาการมอบหมายที่ดีที่สุดผ่านเส้นทางเพิ่ม

สำหรับเมทริกซ์สี่เหลี่ยมผืนผ้า เพิ่มแถวหรือคอลัมน์จำลองที่มีต้นทุน 0 ตัวแทนหรืองานที่ไม่ได้มอบหมายจะถูกรายงานแยก

Formula: หาค่าต่ำสุด Σ C[i][σ(i)] สำหรับทุก i ภายใต้เงื่อนไขว่า σ เป็นเพอร์มิวเทชัน (การจับคู่แบบหนึ่งต่อหนึ่ง) ขั้นตอนวิธีฮังการี: 1. ลบค่าต่ำสุดของแต่ละแถว 2. ลบค่าต่ำสุดของแต่ละคอลัมน์ 3. ขีดเส้นคลุมศูนย์ด้วยจำนวนเส้นน้อยที่สุด 4. ปรับเมทริกซ์แล้วทำซ้ำจนได้คำตอบที่เหมาะสมที่สุด

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

เมทริกซ์ต้นทุน: [[9,2,7],[6,4,3],[5,8,1]] ลดแถว → [[7,0,5],[3,1,0],[4,7,0]] ลดคอลัมน์ → [[4,0,5],[0,1,0],[1,7,0]] ช่องศูนย์ให้งานละหนึ่งแก่แต่ละตัวแทน: ตัวแทน 1→งาน 2 (ต้นทุน 2) ตัวแทน 2→งาน 1 (ต้นทุน 6) ตัวแทน 3→งาน 3 (ต้นทุน 1) ต้นทุนรวม = 9 — ต่ำกว่าการจับคู่ที่ดูน่าเลือกอย่าง ตัวแทน 2→งาน 3, ตัวแทน 3→งาน 1 (10)

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

• หัวหน้างานฝ่ายผลิตที่จัดสรรพนักงานให้กับเครื่องจักรเพื่อให้เวลาหรือต้นทุนการผลิตรวมต่ำที่สุด
• ผู้จัดการโครงการที่จัดสรรสมาชิกทีมให้กับงานตามความเหมาะสมของทักษะและประมาณการภาระงาน
• ผู้ประสานงานโลจิสติกส์ที่จัดสรรรถขนส่งให้กับเส้นทางเพื่อให้ระยะทางเดินทางรวมต่ำที่สุด
• ผู้บริหารมหาวิทยาลัยที่จัดห้องสอบให้กับรายวิชาเพื่อลดความขัดแย้งของตารางหรือระยะทางเดิน

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

• กรอกต้นทุนอย่างไม่สอดคล้องกัน — ค่าทั้งหมดในเมทริกซ์ต้นทุนต้องใช้หน่วยเดียวกัน (เงิน ชั่วโมง ระยะทาง); การปนหน่วยจะให้ผลการมอบหมายที่ไร้ความหมาย
• ลืมสลับระหว่างโหมด minimize กับ maximize — หากมอบหมายตามกำไรหรือความชอบ (ยิ่งสูงยิ่งดี) ให้เลือก maximize; หากเป็นต้นทุนหรือเวลา (ยิ่งต่ำยิ่งดี) ให้เลือก minimize
• ใช้ปัญหาการมอบหมายกับโจทย์ที่ตัวแทนหนึ่งคนรับได้หลายงาน — อัลกอริทึมฮังการีจับคู่ตัวแทนแต่ละคนกับงานเพียงหนึ่งงานเท่านั้น; หากตัวแทนรับได้หลายงาน ให้ใช้โมเดลอื่น
• ไม่จัดการคู่ที่เป็นไปไม่ได้ — หากคู่ตัวแทน-งานบางคู่เป็นไปไม่ได้ ให้ตั้งต้นทุนเป็นตัวเลขที่ใหญ่มากแทนที่จะปล่อยเป็นศูนย์

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

• ต้นทุนรวมคือคำตอบที่เหมาะสมที่สุดแบบสากล — ไม่มีการจับคู่แบบหนึ่งต่อหนึ่งแบบอื่นใดที่ให้ผลรวมต่ำกว่า (หรือสูงกว่า ในกรณี maximization) ได้
• หากมีแถวหรือคอลัมน์ที่ระบุว่าไม่ได้รับมอบหมาย แสดงว่ามีตัวแทนมากกว่างาน (หรือกลับกัน) — ตัวแทน/งานเหล่านี้จะยังว่างอยู่
• เปรียบเทียบผลรวมที่เหมาะสมที่สุดกับการมอบหมายแบบตรงไปตรงมา (เช่น แถว 1 จับคู่คอลัมน์ 1) เพื่อดูว่าอัลกอริทึมช่วยปรับปรุงได้มากเพียงใด

มาตรฐานและเอกสารอ้างอิง

• Kuhn, H. W. (1955), 'The Hungarian Method for the Assignment Problem', Naval Research Logistics Quarterly — งานตีพิมพ์ต้นฉบับของอัลกอริทึม
• Munkres, J. (1957), 'Algorithms for the Assignment and Transportation Problems', Journal of the SIAM — การปรับปรุงที่ยืนยันเวลาการทำงานแบบพหุนาม
• Burkard, Dell'Amico & Martello (2009), Assignment Problems (SIAM) — เอกสารอ้างอิงสมัยใหม่ที่ครอบคลุมโมเดลและอัลกอริทึมการมอบหมายงาน

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

สามารถทำการเพิ่มสูงสุดได้หรือไม่?

ได้ เปลี่ยนเครื่องหมายต้นทุนทั้งหมดหรือลบจากค่าสูงสุด แล้วแก้ปัญหาการลดต่ำสุด การมอบหมายที่ดีที่สุดเหมือนกัน

ถ้าจำนวนคนงานและงานไม่เท่ากัน?

อัลกอริทึมเพิ่มแถวหรือคอลัมน์จำลองที่มีต้นทุน 0 การมอบหมายไปยังรายการจำลองหมายถึงคนงานหรืองานที่ไม่ได้มอบหมาย

ปัญหาการมอบหมายงานรองรับข้อจำกัดในโลกจริง เช่น ทักษะหรือความพร้อมของพนักงานได้หรือไม่?

ไม่ได้โดยตรงในรูปแบบพื้นฐาน อย่างไรก็ตาม คุณสามารถระบุการมอบหมายที่เป็นไปไม่ได้โดยตั้งต้นทุนของคู่นั้นให้เป็นตัวเลขที่ใหญ่มาก (เช่น 999999) ซึ่งจะป้องกันไม่ให้อัลกอริทึมเลือกคู่นั้นโดยปริยาย สำหรับข้อจำกัดที่ซับซ้อน ควรพิจารณาใช้ตัวแก้ปัญหา integer linear programming