TAILIEUCHUNG - 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

• Tự động hoá
• Bài toán lập lịch
• khoa học điều khiển
• hệ thống kỹ thuật
• điều khiển học
• nghiên cứu tin học
• Lý thuyết thuật toán
• tự động học
• Điện toán đám mây
• Mô hình luồng công việc
• Bài toán lập lịch Workflow
• Công cụ mô phỏng CloudSim
• Tài nguyên mạng
• Thuật toán Johnson
• Thuật toán More
• Lập lịch ưu tiên đúng hạn
• gia công máy
• Kỷ yếu hội nghị Quốc gia về Điện tử truyền thông
• Thuật toán LPSO lập lịch
• Ứng dụng khoa học trong môi trường
• Giải thuật tối ưu hóa rừng cây
• Lưới tính toán
• Công việc độc lập
• Giải thuật FOA
• Gieo mầm cục bộ
• Giải thuật lập lịch
• Thuật toán lập lịch
• Lập lịch Scheduling
• Lập lịch multiprocessor
• Hệ điều hành
• Bài giảng hệ điều hành
• Tạp chí khoa học
• Thuận toán MODE
• Giải Bài toán lập lịch luồng công việc
• Luồng công việc
• Tập lịch trình công việc
• Tiến hóa khác biệt
• Tối ưu đa mục tiêu
• Tối ưu đa mục tiêu lập lịch
• hệ thống tính toán lưới
• Thuật toán di truyền
• Hàm đo độ thích nghi
• Luận án tiến sĩ
• Luận án tiến sĩ Toán học
• Cơ sở toán học cho tin học
• Bài toán Lập lịch luồng
• Nguyên lý hệ điều hành
• Bài giảng Nguyên lý hệ điều hành
• Lập lịch CPU
• Phương pháp đánh giá thuật toán lập lịch
• Lập lịch công việc
• Phương pháp PSO
• Chi phí truyền tải dữ liệu
• Giải Thuật Di Truyền Ứng Dụng
• Giải Bài Toán Lập Lịch
• luận văn
• thiết kế hệ thống
• lập trình hệ thống
• xây dựng phần mềm
• kỹ thuật lập trình
• Lịch luồng công việc
• Thuật toán lập lịch luồng công việc
• Thuật toán metaheuristic PSOi
• Phương pháp tối ưu bầy đàn
• Hệ số quán tính
• Hệ số gia tốc
• Phương pháp tiến hóa vi phân
• Lập lịch luồng công việc
• Tìm kiếm Tabu
• Tối ưu bày đàn
• Dịch vụ công nghệ
• Luận án Tiến sĩ Khoa học máy tính
• Khoa học máy tính
• Tính toán đám mây
• Bài toán lập lịch trên tính toán đám mây
• Quản lý tài nguyên
• Lập lịch tác vụ
• Thuật toán heuristic
• Bài toán NP đầy đủ
• Bài toán lập lịch luồng công việc
• Phương pháp nhánh cận
• Công nghệ thông tin
• Bài toán lập lịch cá nhân
• Quy hoạch toán học
• Phương pháp heuristic
• Phương pháp metaheuristic
• Ứng dụng luồng công việc
• Phương pháp nhánh cận
• Tài nguyên thực dùng
• Thi Công Công Trình
• luận văn tốt nghiệp
• báo cáo thực tập
• đề tài tiểu luận
• Luận văn Thạc sĩ
• Luận văn Thạc sĩ Khoa học máy tính
• Nghiên cứu bài toán lập lịch
• Hệ thống xếp thời khóa biểu
• Phương pháp tối ưu hóa đàn kiến
• Bài giảng Thuật toán Ứng dụng
• Thuật toán Ứng dụng
• Thuật toán Tham lam
• Ý tưởng tham lam
• Tiếp cận tham lam
• Bài giảng Tin học đại cương
• Tin học đại cương
• Thuật toán và ngôn ngữ lập trình
• Phương pháp giải quyết vấn đề bằng máy tính
• Lịch sử phát triển ngôn ngữ lập trình
• giao thông
• vận tải
• mạng giao thông công cộng
• mô hình toán học
• thiết lập lịch trình vận tải