tailieunhanh - Bài toán lập lịch trong các trường đại học và thuật toán Tabu.

Bài toán lập lịch trong các trường đại học và thuật toán Tabu. Các nhà Điều khiển học và khoa học hệ thống - Norbert Wiener (1894-1964) nhà toán học; sáng lập ra ngành Điều khiển học. W. Ross Ashby (1903-1972) một trong số những người sáng lập ra ngành điều khiển học; phát triển khái niệm cân bằng nội (homeostat), quy luật về sự đa dạng cần thiết, nguyên lý tự tổ chức, và quy luật về sự điều chỉnh mô hình. . | Tạp chí Tin học và Điều khiền học 2005 99--107 BÀI TOÁN LẬP LỊCH TRONG CÁC TRƯỜNG ĐẠI HỌC VÀ THUẬT TOÁN TABU BÙI MINH TRÍ NGUYỄN NHƯ HẠNH Trường Đại học Bách khoa Hà nội Abstract. This paper presents a reformation of Tabu search approach and its application to solving the timetabling problem for universities. Tóm tắt. Bài báo này trình bày một cải tiến của phương pháp tìm kiếm Tabu và áp dụng vào bài toán lập lịch cho các trường đại học. 1. MÔ HÌNH BÀI TOÁN XEP LỊCH CHO CÁC BÀI GIẢNG Bài toán xếp lịch học là một bài toán phân bổ tài nguyên trong đó các hoạt động là các bài giảng i i 1 n các tài nguyên là các thời điểm j j 1 m trong tuần mỗi thời điểm được xét là bắt đầu một tiết học . Mục tiêu của bài toán này là xác định một thời khoá biểu không mâu thuẫn và thoả mãn nhiều nhất nguyện vọng của giáo viên. Hai bài giảng được xem là xung đột nếu diln ra đồng thời ít nhất có một phần thời gian và yêu cầu một trong các điều kiện sau cùng một giáo viên cùng một phòng học hai bài giảng có chung sinh viên hoặc cùng cho một lớp. Để tính đến việc thoả mãn yêu cầu của giáo viên ta đưa vào biến Xịj nhận giá trị 1 nếu giáo viên dạy bài giảng i tại thời điểm j bằng 0 nếu ngược lại và hệ số Cịj là điểm mà giáo viên dạy bài giảng i tại thời điểm j cho theo nguyện vọng tại các thời điểm đã chọn theo thứ tự nguyện vọng tốt nhất thì cho điểm 1 rồi đến điểm 2 . Nó có ý nghĩa là giáo viên thích dạy bài giảng đó ở thời điểm nào và không thích ở thời điểm nào. Bài toán lúc này có mô hình là n m F x EE CijXij -ì- min 1 j l d . d ro d1 dẤ Pl 2_ Xij 1 ỉ Xij E 0 1 . 1 j i Xij I 1 l ẽ Jịjk i k n i j . 2 trong đó Jijk là tập các thời điểm l mà nếu phân cho bài giảng k thì sẽ xảy ra xung đột với bài giảng i được phân tại thời điểm j. Mô hình bài toán trên là bài toán quy hoạch nguyên 0 1 với số lượng các ràng buộc là rất lớn. Điều kiện 1 đảm bảo rằng mỗi bài giảng chỉ được phân bổ vào một thời điểm trong tuần. Điều kiện 2 đảm bảo không xảy ra xung đột giữa hai bài giảng. Nhưng