Cách giải bài phân công công việc

[Phong_Thuan (Phong Thuận)]

Trình bày một thuật giải heuristic có thể áp dụng để giải bài toán phân công sau đây:
Có n công việc sẽ được phân cho m người thực hiện, mỗi việc được phân cho một người.
Giả sử ta biết thời gian tij cần để người thứ i thực hiện công việc thứ j (i=1,…, m; j=1,…, n). Hãy
tìm một phương án phân công sao cho thời gian hoàn thành tất cả các công việc là thấp nhất (tính
từ khi mọi người cùng bắt đầu thực hiện các công việc được phân công cho tới khi tất cả các công
việc đều được thực hiện xong).
Kiểm tra kết quả thực hiện thuật giải cho trường hợp n = 8, m = 3, và các tij được cho trong
bảng dưới đây:
5 5 4 10 8 6 12 8
7 5 7 3 9 7 8 5
10 6 7 8 10 6 5 7