Báo Cáo Tìm hiểu bài toán phân công công việc và demo

gồm 1 bản word và 1 sile thuyết trình


I, Bài toán phân công công việc
1, Nội dung bài toán
Một đề án gồm n công việc và các việc sẽ được thực hiên bởi m máy như nhau.
Giả sử biết thời gian để 1 máy thực hiện viêc thứ j là tj
Yêu cầu: Tìm phương án phân công sao cho thời gian hoàn thành toàn bộ công việc là thấp nhất.
Mẫu số liệu : n=10, m=3
tj = 4 9 5 2 7 6 10 8 7 5
2, Giải thuật: được viết dưới dạng thủ tục tương tự như thuật toán nhưng không đòi hỏi các tiêu chuẩn như thuật toán.
- Tính đúng: chấp nhận các giải thuật đơn giản, có thể cho kết quả đúng hay gần đúng nhưng có khả năng thành công cao hơn.
- Để có thể được chấp nhận, giải thuật phải thể hiện một giải pháp hợp lý nhất có thể trong tình huống hiện tại bằng cách:
+ Tận dụng mọi thông tin hữu ích
+ Sử dụng tri thức, kinh nghiệm trực giác của con người
+ Tự nhiên, đơn giản nhưng cho kết quả chấp nhận được
è Giải thuật Heuristic
Giải thuật cho bài toán phân công đơn giản:
Chọn việc J chưa phân công có thời gian thực hiện cao nhất phân công cho máy có thời gian làm việc thấp nhất
for(k=0;k<n;k++)
{
Chọn việc J chưa phân công có thời gian thực hiện cao nhất.
Chọn máy M có thời gian làm việc thấp nhất
Bố trí việc J cho máy M.