Giải bài toán phân công

Bài toán phân công là gì?

Bài toán phân công là bài toán tối ưu tổ hợp cơ bản: cho n tác nhân và n nhiệm vụ với ma trận chi phí C, tìm phân công một-một tối thiểu hóa tổng chi phí. Xuất hiện trong lập lịch nhân lực, phân bổ xưởng, định tuyến xe.

Thuật toán Hungary (phương pháp Kuhn-Munkres, 1955) giải trong O(n³). Nó giảm ma trận chi phí lặp đi lặp lại qua trừ hàng và cột, sau đó tìm phân công tối ưu qua đường tăng trong đồ thị hai phần.

Với ma trận chữ nhật, thêm hàng hoặc cột giả có chi phí 0 để làm vuông. Các tác nhân hoặc nhiệm vụ chưa phân công được báo cáo riêng.

Formula: Cực tiểu hóa Σ C[i][σ(i)] với mọi i với điều kiện σ là một hoán vị (ánh xạ một-một) Các bước Hungarian: 1. Trừ giá trị nhỏ nhất của từng hàng 2. Trừ giá trị nhỏ nhất của từng cột 3. Phủ các số 0 bằng số đường tối thiểu 4. Điều chỉnh ma trận, lặp lại đến khi tối ưu

Ví dụ tính toán

Ma trận chi phí: [[9,2,7],[6,4,3],[5,8,1]]. Rút gọn hàng → [[7,0,5],[3,1,0],[4,7,0]]. Rút gọn cột → [[4,0,5],[0,1,0],[1,7,0]]. Các ô 0 cho mỗi tác nhân một nhiệm vụ: Tác nhân 1→Nhiệm vụ 2 (chi phí 2), Tác nhân 2→Nhiệm vụ 1 (chi phí 6), Tác nhân 3→Nhiệm vụ 3 (chi phí 1). Tổng chi phí = 9 — thấp hơn cách ghép dễ thấy Tác nhân 2→Nhiệm vụ 3, Tác nhân 3→Nhiệm vụ 1 (10).

Khi nào sử dụng công cụ này

• Giám sát sản xuất phân công công nhân vào máy để tối thiểu hóa tổng thời gian gia công hoặc chi phí
• Quản lý dự án phân bổ thành viên nhóm vào các nhiệm vụ dựa trên mức độ phù hợp kỹ năng và ước lượng công sức
• Điều phối viên logistics phân công xe giao hàng vào các tuyến để tối thiểu hóa tổng quãng đường di chuyển
• Quản trị viên trường đại học xếp phòng thi cho các môn học để tối thiểu hóa xung đột hoặc quãng đường di chuyển

Những sai lầm thường gặp

• Nhập chi phí không nhất quán — mọi giá trị trong ma trận chi phí phải dùng cùng đơn vị (tiền, giờ, khoảng cách); trộn lẫn đơn vị tạo ra phân công vô nghĩa
• Quên chuyển giữa chế độ cực tiểu và cực đại — nếu phân công theo lợi nhuận hoặc mức ưu tiên (càng cao càng tốt), chọn cực đại; với chi phí hoặc thời gian (càng thấp càng tốt), chọn cực tiểu
• Dùng bài toán phân công cho trường hợp mỗi tác nhân nhận nhiều nhiệm vụ — thuật toán Hungarian gán mỗi tác nhân đúng một nhiệm vụ; nếu tác nhân có thể đảm nhận nhiều nhiệm vụ, hãy dùng mô hình khác
• Không xử lý các cặp ghép bất khả thi — nếu một số tổ hợp tác nhân-nhiệm vụ là không thể, hãy đặt chi phí của chúng thành một số rất lớn thay vì để bằng 0

Cách diễn giải kết quả

• Tổng chi phí thể hiện nghiệm tối ưu toàn cục — không có phép gán một-một nào khác đạt tổng thấp hơn (hoặc cao hơn, với bài toán cực đại)
• Nếu một số hàng hoặc cột được liệt kê là chưa gán, nghĩa là số tác nhân nhiều hơn số nhiệm vụ (hoặc ngược lại) — các tác nhân/nhiệm vụ này còn trống
• So sánh tổng tối ưu với phép gán thô sơ (ví dụ: hàng 1 vào cột 1) để thấy thuật toán cải thiện được bao nhiêu

Tiêu chuẩn và tài liệu tham khảo

• Kuhn, H. W. (1955), 'The Hungarian Method for the Assignment Problem', Naval Research Logistics Quarterly — công bố gốc của thuật toán
• Munkres, J. (1957), 'Algorithms for the Assignment and Transportation Problems', Journal of the SIAM — cải tiến xác lập thời gian chạy đa thức
• Burkard, Dell'Amico & Martello (2009), Assignment Problems (SIAM) — tài liệu tham khảo hiện đại toàn diện về các mô hình và thuật toán phân công

Câu hỏi thường gặp

Bài toán phân công có thể tối đa hóa không?

Có. Phủ định tất cả chi phí hoặc trừ từ giá trị lớn nhất, rồi giải bài toán tối thiểu hóa. Phân công tối ưu giống nhau, chỉ dấu thay đổi.

Nếu số công nhân và công việc không bằng nhau?

Thuật toán thêm hàng hoặc cột giả có chi phí 0. Phân công vào mục giả biểu thị công nhân hoặc công việc chưa được phân công.

Bài toán phân công có xử lý được các ràng buộc thực tế như kỹ năng hay lịch rảnh của công nhân không?

Không xử lý trực tiếp trong dạng cơ bản. Tuy nhiên, bạn có thể mã hóa các phân công bất khả thi bằng cách đặt chi phí của chúng thành một số rất lớn (ví dụ: 999999), qua đó ngăn thuật toán chọn chúng. Với các ràng buộc phức tạp, hãy cân nhắc dùng bộ giải quy hoạch tuyến tính nguyên.