CHƯƠNG 1. MỞ DAU Chương này giới thiệu về dé tai, mục đích của nghiên cứu và nêu phương pháp nghiên cứu. TONG QUAN VE CÁC CÔNG TRINH LIÊN QUAN Chương này sẽ nêu lên các công trình có liên quan đến dé tài và các nhận xét cá nhân. CƠ SỞ LY THUYET Chương này sẽ trình bảy nội dung cơ sở lý thuyết để giải quyết bài toán: khái niệm liên quan đến hệ hỗ trợ ra quyết định; giải thuật tô màu đồ thị, heuristic bậc lớn nhất của đỉnh; bài toán tối ưu ; giải thuật tham lam; giải thuật AHP.
MÔ HINH BÀI TOÁN Trang 3 Chương này trình bày mô hình bai toán xếp lịch, bao gồm: nội dung bài toán, các ràng buộc, các tham số liên quan và giải thuật dùng để giải quyết bai toán. Mô phỏng giải thuật trên dữ liệu thực tế. HIỆN THUC CHƯƠNG TRÌNH Chương này sẽ trình bày chi tiết phần hiện thực hệ thông xếp lịch. KET QUA THỰC NGHIỆM Chương này trình bay kết qua thực nghiệm va các biéu đồ dựa trên các tham sé thực nghiệm.
Từ đó rút ra các nhận xét và đánh giá. TONG KET DANH GIA Chương nay tong kết lai những gi đã làm được, những hạn chế va hướng phat triền. Trang 4 Chương 2: TONG QUAN CAC CONG TRINH LIEN QUAN Chương này sẽ trình bay một số công trình liên quan va các nhận xét. Các giải thuật xếp thời khóa biểu 2.
Ung dung giải thuật tô mau đồ thị Tác giả Carter (1986) đã có một khảo sát về việc ứng dụng giải thuật tô màu đô thị dé giải quyết bài toán xếp thời khóa biéu, trong đó đã nêu ra rất nhiều công trình của các tác giả khác nhau đã ứng dụng giải thuật tô màu đô thị cho việc xếp lich học va lịch thi. Về quy hoạch toán học Đã có rất nhiều tác giả đã xây dựng các công trình của mình trong đó sử dụng mô hình quy hoạch toán học như là: Birbas, Daskalaki & Housos (1997) [9], Tripathy (1984) [13], Tripathy (1992) [19] và Daskalaki, Birbas & Housos (2004) [14] 2. Về lập trình rang buộc Omer S. Reha Botsali (2004) [15] đã xây dựng một hệ hỗ trợ ra quyết định trong đó kết hợp cả lập trình ràng buộc va quy hoạch toán hoc dé giải quyết bai toán xếp thời khóa biểu.
Ngoài ra SYLVAIN PIECHOWIAK, CHRISTOPHE KOLSKI (2003) [16] cũng đã sử dụng lập trình ràng buộc dé xây dựng một hệ hỗ trợ ra quyết định cho vân đề xếp thời khóa biểu. Meta-heuristic mô phỏng luyện kim Johnson (1990) [22] đã sử dụng mô phỏng luyện kim cho mô hình của mình với một tập rất lớn các biến nhị phân đề xếp lịch thi. Meta-heuristic tim kiếm Tabu Tác giả Quan Thanh Tho và Nguyễn Tuấn Anh của trường cao đăng Nguyễn Tất Thành đã xây dựng một “HỆ THONG RA QUYET ĐỊNH SẮP THỜI KHÓA BIEU THONG MINH” [3]. ở đây tác giả đã ứng dụng giải thuật Trang 5 Tabu dé xây dựng một Module xếp thời khóa biểu thông minh và một kiến trúc cho phép tích hop module nay vào bat kì hệ thống có sẵn nào.
Meta-heuristic giải thuật di truyền Khi giải thuật di truyền ra đời thì đã có rât nhiều ứng dụng trong việc giải quyết các loại bài toán khác nhau, trong đó có thé áp dung để giải quyết van dé xếp thời khóa biểu. Đã có rat nhiều công trình xếp thời khóa biểu ứng dụng giải thuật di truyền, ta có thé tim thấy nó trong một khảo sát của các tác gia Corne, Ross & Fang (1994) [23] and Burke & Petrovic (2002) [6]. Ngoài ra Ulrich Derigs and Olaf Jenal(2005) [18] cũng đã xây dung một hệ hỗ trợ quyết định sử dung giải thuật di truyền cho van dé xếp thời khóa biểu.Các hệ hỗ trợ quyết định xếp thời khóa biểu 2. A GA-based decision support system for professional course scheduling at Ford Service Organisation, Ulrich Derigs and Olaf Jenal, 2005.
—Tac giả Ulrich Derigs and Olaf Jenal [18] đã xây dựng một hệ hỗ trợ quyết định xếp thời khóa biểu cho các khóa học chuyên nghiệp tại trung tâm dịch vụ Ford. —Phan cốt lõi của hệ hỗ trợ quyết định này chính là việc sử dung Meta — heuristic giải thuật đi truyền (GA) để tạo lập một hệ thống xếp thời khóa biểu cho phép người lập kế hoạch có thể tạo ra, đánh gia và so sánh được sự khác nhau của các thời khóa biểu đã được tạo ra băng cách là chạy chương trình với số lần khác nhau dựa trên sự thay đổi hàm mục tiêu và những chiến lược xếp đặt khác nhau, ví dụ như cho phép xếp đặt trước một tập con của khóa học nào đó vào những phòng cụ thể, các giáo viên cụ thể. Hệ hỗ trợ quyết định này được hiện thực như là một dịch vu Web, trong đó việc giao tiếp với web được thực hiện thông qua Internet. —Phương pháp GA có ý nghĩa quan trọng với DSS, nó cho phép người lập lịch có thé tạo ra một lịch (gan) tối ưu, và DSS cũng cho phép anh ta thực hiện được những phân tích What-if và tìm kiếm mục tiêu mà không phải mat Trang 6 quá nhiều thao tac và quá nhiều ràng buộc mềm hay hàm mục tiêu.
> Ddy chính là những diéu mà DSS can! 2. Johnson, SlotManager: a microcomputer- based decision support system for university timetabling, Decision Support Systems 27 (2000) 367 — 381 -Bài báo nay, tác giả giới thiệu một DSS xếp thời khóa biểu trường học với giao diện thân thiện, menu x6 xuống [17]. Điều đặc biệt là hệ thống được viết bằng MS Access, môi trường Windows. Hệ thống đã cung cấp những tính năng tiện dụng, quan trọng và có những ứng dụng theo hướng hệ hỗ trợ ra quyết định.
-Mặc dù là DSS chuyên dụng nhưng cũng dễ dang trở nên phổ dụng vì nó có thé tự do thay đối những yêu cầu khác nhau cho phù hợp nhu cầu. Slotmanager được chia làm 3 thành phan chính của hệ hỗ trợ ra quyết định: vé Giao diện người dùng. * Cơ sở mô hình. * Cơ sở dữ liệu —Slotmanager được hiện thực với mạng cục bộ cung cấp truy cập tới các tập tin cơ sở dữ liệu lưu trữ ở trung tâm.
DSS được phát triển băng cách xây dựng các prototype ( các phiên bản dạng như là bản nháp, làm ra chỉ dé thử nghiệm, sau đó sẽ bỏ đi, cứ tiếp tục như thế và phát triển dần cho đến khi hoàn chỉnh). Đây là cách phổ biến nhất trong quy trình xây dựng một DSS. Các yêu cầu thêm vào, các chỉnh sửa được hoàn thiện dan tại mỗi giai đoạn. Bang cách phát triển dan từ các prototype, người dùng thử nghiệm có thé đưa ra được các phản hỏi có giá trị đối với việc hoàn thiện DSS.
=Hướng tiếp cận của tác giả không phải là việc tạo tự động một thời khóa biểu mà nỗ lực dé làm thỏa tất cả các ràng buộc và loại bỏ những phiền toái đã tồn tại. Hơn thé nữa, mục đích của DSS là hỗ trợ người lập lịch tạo ra một thời khóa biểu từ thời điểm ban dau hoặc hiệu chỉnh thời khóa biểu đã tôn tại, kiểm tra độ xung đột của nó. Và một điều quan trọng nữa là DSS hoàn Trang 7 toàn không hé thay thế người ra quyết định, mà chỉ hỗ trợ người xếp lịch một cách có hiệu quả. —Slotmanager hau như có tat cả các tính năng cơ bản của một DSS, từ khâu thiết kế, hiện thực cho đến hệ thông.
Nó hỗ trợ những quyết định ban cấu trúc, ở đó phân tích what — if cũng có thé được hệ thống hóa. Slotmanager hỗ trợ tat cả các giai đoạn ra quyết định. Nó kết hợp cơ sở dữ liệu, cơ sở mô hình và các kỹ thuật trình bày kết quả. Nó chú trọng đến tính năng dễ sử dụng, giao diện thân thiện: dé dàng điều khiển, linh hoạt và thích nghi.
Có thé tương tác kha dé dang với các hệ thống máy tính khác dé thực hiện công việc download va upload thông tin. An Optimization-Based Decision Support System for a University Timetabling Problem: An Integrated Constraint and Binary Integer Programming Approach — Omer S. Reha Botsali [1Š| đã xây dung một hệ hỗ trợ quyết định xếp thời khóa biéu dựa trên lập trình ràng buộc (CSP) và quy hoạch nguyên nhi phân. — Câu trúc của bài toán CSP gôm co: tập các biến, mỗi biến có một miền trị tương ứng với nó, tập các ràng buộc trên các biến.
— Vi bài toán xếp thời khóa biểu thuộc lớp NP-Complete, khi kích thước của bài toán tăng thì thời gian tính toán tăng nhanh và rất khó để tìm ra lời giải trong thời gian có thé chấp nhận được. Để khắc phục van dé này, tập những ràng buộc sẽ được chia nhỏ thành những tập con. Bây giờ bài toán xếp thời khóa biểu là sự tô hợp của những bài toán con để giải quyết van dé xếp giờ học cho mỗi ngày, sau đó thực hiện việc xếp phòng học cho giờ học tương ứng. Bài toán được giải quyết qua ba giai đoạn: 2 giai đoạn dau là xây dựng mô hình cho bai toán và giải quyết việc xếp giờ học cho các môn học bằng lập trình ràng buộc, giai đoạn 3 là xếp phòng học cho lớp học đã xếp băng quy hoạch nguyên nhị phân.
— Hệ thống có 3 thành phan chính đó là: ¥ Co sở mô hình. Trang 8 ¥ Co sở dit liệu. ¥ Giao diện người dùng. — Quan điểm hệ hỗ trợ quyết định năm ở chỗ: người lập lịch có thé thêm vào hay loại bỏ các ràng buộc từ đó có thể đạt được những thời khóa biểu khác nhau va có thé so sánh chúng dé chọn ra thời khóa biểu thích hợp.
Towards a Generic Object Oriented Decision Support System For University Timetabling: An Interactive Approach — Tac gia SYLVAIN PIECHOWIAK va CHRISTOPHE KOLSKI [16] đã sử dụng lập trình ràng buộc dé xay dung hé thong. Hệ thống là một hệ hỗ trợ ra quyết định dé quan lý thời khóa biểu cho trường dai học với 3 tiêu chí: tiêu chí thứ nhất là xây dựng một công cụ rõ ràng, có thể phát triển trong nhiều cách khác nhau, để đạt được điều này tác giả xây dựng theo hướng tiếp cận hướng đối tượng, định nghĩa những đối tượng chỉ định cho thời khóa biểu; tiêu chí thứ hai là phải xây dựng một mô hình câu trúc tốt cho thời khóa biểu; tiêu chí cuối cùng là tinh dé sử dụng đối với nhiều đối tượng người dùng khác nhau. — Các bước dé xây dựng hệ hỗ trợ ra quyết định gồm: thu thập yêu cau; phân tích yêu cau can thiết cho hệ thống: xây dựng mô hình; mô tả hệ ràng buộc; — Quan điểm hỗ trợ quyết định của hệ thống theo tác giả năm ở chỗ: hệ thống được xây dựng phải có khả năng tương thích cao.
