MÔ HÌNH GIAO VIỆC

Nguyễn Như Phong

Kỹ thuật Hệ thống Công nghiệp

Đại học Bách Khoa TPHCM

a. Bài toán giao việc

Bài toán giao việc là bài toán phân công n công việc cho n công nhân, mỗi người một việc, chi phí giao việc j, j=1–n cho công nhân i, i=1–n là cij. Mục tiêu của bài toán là xác định kế họach phân công sao cho tổng chi phí phân công là nhỏ nhất.

Giả sử số lượng công nhân và số lượng công việc như nhau không làm mất tính tổng quát của bài toán, vì khi số lượng công nhân nhiều hơn số lượng công việc ta có thể cân bằng bài toán như ở bài toán vận tải bằng cách thêm các công việc ảo. Ngược lại, nếu số lượng công nhân ít hơn số lượng công việc ta có thể cân bằng bài toán như ở bài toán vận tải bằng cách thêm các công nhân ảo.

Mô hình giao việc là một trường hợp đặc biệt của mô hình vận tải, các công nhân được xem là những điểm nguồn với lượng cung ở mỗi nguồn là 1. Các công việc được xem là những điểm đích với lượng cầu ở mỗi đích là 1. Kế họach vận tải vận tải công nhân đến các công việc sao cho chi phí là thấp nhất.

Mô hình giao việc với n công nhân W_i, i=1–n và n công việc J_j, j=1–n có bảng giao việc như sau:

b.  Phương pháp Hungary

Mô hình giao việc là một trường hợp đặc biệt của mô hình vận tải nên có thể giải bởi giải thuật vận tải. Tuy nhiên vì có cấu trúc đặc biệt, mọi lượng cung ở các nguồn và mọi lượng cầu ở các điểm đích đều bằng 1 nên có thể giải bằng giải thuật giao việc đơn giản hơn giải thuật vận tải.

Giải thuật giao việc thường dùng là phương pháp Hungary được minh họa qua bài toán giao việc với ba công nhân và ba công việc với chi phí giao việc như ở bảng sau

Phương pháp Hungary gồm ba bước:

1. Từ ma trận chi phí, với mỗi hàng xác định chi phí cực tiểu ở mỗi hàng và trừ giá trị này cho toàn hàng tương ứng.
2. Từ ma trận chi phí thu được ở bước 1, với mỗi cột, xác định chi phí cực tiểu ở mỗi cột và trừ giá trị này cho toàn cột tương ứng.
3. Xác định phân công tối ưu bằng phân công khả thi dựa vào các ô có giá trị là 0 ở ma trận chi phí thu được ở bước 2. Khi chọn các ô có giá trị là 0 cần lưu ý tính khả thi bằng cách không chọn các ô cùng hàng hay cùng cột.

TLTK

Nguyễn Như Phong. Vận trù xác định. NXBĐHQG. 2010