 |
CHƯƠNG
3. XẾP LỊCH CÔNG VIỆC
Bài toán xếp lịch công việc được xét
trong nhiều vấn đề thực tế khác nhau: giao việc, gia công các chi tiết
trên máy, đóng gói hàng hoá vào một hoặc nhiều thùng, xếp lịch thi đấu, lịch học
tập, hành trình du lịch, chọn đối tượng và phương án thi công, bài toán vận tải
xếp hàng, điều hành xe, chọn địa điểm xây dựng nhà máy, kế hoạch sản xuất các sản
phẩm, xếp thời khoá biểu công việc... Trong những dạng trên có nhiều bài chưa thể giải tối ưu trong thời gian cho phép
(chỉ có thể chọn ra phương án tương đối thích hợp với điều kiện dữ liệu cụ thể
nào đó), hơn nữa nhiều bài dưới dạng tổng quát còn được xếp vào lớp bài toán
còn mở - đến nay chưa có thuật toán hữu hiệu - do đó trong tài liệu này chúng
tôi chỉ hạn chế nêu một số bài tập gặp trong các kỳ thi học sinh giỏi Tin học
trước đây và nêu một số cách giải thích hợp đáp ứng được yêu cầu kỳ thi. Qua giới
thiệu bài tập chúng tôi cố gắng minh hoạ một số phương pháp thường gặp nhất
trong bài toán lập lịch.
|
Nội dung của chương gồm:
I - Lý thuyết và bài tập minh hoạ (15 bài –
thuật toán, cài đặt dữ liệu và chương trình)
A - Biết lịch, tìm đặc
điểm của lịch
B - Biết đặc điểm của
lịch, tìm lịch tối ưu
1. Phương pháp sắp xếp topo
2.
Thuật toán Johnson
3.
Phương pháp Heuristic
4.
Phương pháp duyệt có đặt cận (kết hợp greedy)
5.
Quy hoạch động
6.
Phương pháp làm mịn dần phương án
7.
Thuật toán tối ưu cho một số bài đặc biệt
9.
Phương pháp thế vị.
10.
Phương pháp dựa vào luồng và đồ thị hai phía
II - Các bài tập luyện tập - đề bài và hướng dẫn
giải (18 bài)
III - Các chương trình giải
bài tập phần 2
IV- Bài tập tự giải (11 bài)
|
Hướng dẫn |
