CHƯƠNG 1. GIỚI THIỆU BÀI TOÁN Đại học Quốc gia Hà Nội như sau 2 X min w i di (1.1) i=1 thỏa mãn các ràng buộc cứng 1. Ràng buộc về việc trùng giờ dạy của giảng viên XX ytepr ≤ 1, ∀t ∈ T, ∀p ∈ P, ∀r ∈ R. Ràng buộc về việc trùng giờ học của một lớp chuyên ngành (hay một nhóm sinh viên) xepr − le(p+h)r ≤ 0, ∀e ∈ E, ∀p ∈ P, ∀h ∈ {1, 2,.
Ràng buộc về sự tương thích giữa phòng học và học phần X XX xepr = 0, ∀t ∈ RT, ∀e ∈ Et. Ràng buộc về việc sử dụng trùng phòng học X lepr ≤ 1, ∀p ∈ P, ∀r ∈ R. Ràng buộc về tính liên tục và tính duy nhất về phòng học cho các tiết học của một học phần XX zcepr ≤ 1, ∀c ∈ C, ∀p ∈ P, ∀r ∈ R. Ràng buộc về buổi học cho một học phần xepbi r (pb|Bb | − pbi − ne + 1) ≥ 0, ∀e ∈ E, ∀r ∈ R, ∀b ∈ B, ∀i ∈ {1,.
GIỚI THIỆU BÀI TOÁN 7. Ràng buộc về tính đầy đủ của thời khóa biểu XX xepr = 1, ∀e ∈ E. p∈P r∈R Nhóm các bài toán xếp thời khóa biểu là các bài toán NP-khó, do đó, việc giải các bài toán này bằng phương pháp vét cạn là gần như bất khả thi. Chương thứ hai của luận văn sẽ trình bày một số phương pháp cũng như thuật giải được sử dụng để giải quyết các bài toán thuộc nhóm bài toán này.
12 Chương 2 Các phương pháp giải bài toán xếp thời khóa biểu Từ lúc bài toán thời khóa biểu được Gotlieb đề xuất lần đầu trong bài báo của mình vào năm 1963 [25] cho đến nay, người ta đã đưa ra rất nhiều hướng tiếp cận và thuật giải cho bài toán này. Trong đó, các phương pháp tiêu biểu thường được nghiên cứu và áp dụng cho bài toán xếp thời khóa biểu bao gồm nhóm các phương pháp heuristics trực tiếp, nhóm các phương pháp dựa trên tô màu đồ thị, nhóm các phương pháp quy hoạch ràng buộc, nhóm các phương pháp metaheuristics và nhóm các phương pháp hyperheuristics.1 Các phương pháp heuristics Các phương pháp heuristics thường khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con người. Một phương pháp heuristics thường chỉ được thiết kế để tập trung giải quyết một bài toán cụ thể. Việc giải bài toán sử dụng các phương pháp heuristics thường đơn giản và nhanh chóng nhận được kết quả tốt, tuy có thể không phải là kết quả tốt nhất.
Do đó, các phương pháp heuristics thường được sử dụng để xây dựng lời giải ban đầu cho một số phương pháp khác, như các phương pháp theo hướng metaheuristics và hyperheuristics. Khi xây dựng một phương pháp heuristics cho một bài toán, người ta thường dựa vào một số nguyên lý cơ bản là nguyên lý vét cạn thông minh, nguyên lý tham lam (Greedy) và nguyên lý thứ tự. Trong một bài toán tìm kiếm, khi không gian tìm kiếm 13 CHƯƠNG 2. CÁC PHƯƠNG PHÁP GIẢI BÀI TOÁN XẾP THỜI KHÓA BIỂU lớn, nguyên lý vét cạn thông minh có thể được sử dụng để tìm cách giới hạn lại không gian tìm kiếm hoặc thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu.
Nguyên lý tham lam lấy tiêu chuẩn tối ưu (trên phạm vi toàn cục) của bài toán để làm tiêu chuẩn chọn lựa hành động trong phạm vi cục bộ của từng bước (hay từng giai đoạn) trong quá trình tìm kiếm lời giải. Nguyên lý thứ tự thể hiện qua việc thực hiện các công việc trong từng bước (hoặc từng giai đoạn) dựa trên một cấu trúc thứ tự phù hợp với không gian khảo sát nhằm nhanh chóng đạt được lời giải tốt. Việc xây dựng các phương pháp heuristics thường đi cùng việc xây dựng các hàm heuristics. Đây là các hàm đánh giá thô, giá trị của hàm phụ thuộc vào trạng thái của bài toán tại mỗi bước giải.
Dựa trên giá trị này, ta có thể quyết định được hành động hợp lý cho từng bước của phương pháp.2 Các phương pháp dựa trên tô màu đồ thị Nội dung của bài toán tô màu đồ thị là cho một đồ thị gồm n đỉnh, thực hiện tô màu cho tất cả các đỉnh trong đồ thị sao cho màu của bất kì hai đỉnh kề nhau nào cũng phải khác nhau và số màu sử dụng là ít nhất có thể. Trong khi đó, dạng đơn giản của bài toán xếp thời khóa biểu có thể phát biểu như sau: gán n học phần vào một tập hợp các tiết học sao cho tổng số tiết học cần dùng là cực tiểu. Như vậy, bài toán xếp thời khóa biểu có thể được chuyển hóa thành một bài toán tô màu đồ thị với mỗi học phần đóng vai trò như một đỉnh của một đồ thị, hai đỉnh của đồ thị kề nhau nếu và chỉ nếu hai học phần tương ứng không thể diễn ra trong cùng một tiết, mỗi màu của đồ thị tương ứng với một tiết. Bài toán xếp thời khóa biểu đầu tiên sử dụng phương pháp dựa trên tô màu đồ thị được thực hiện bởi nhóm tác giả Dominic Welsh và Martin B.
Các phương pháp thuộc nhóm này có ưu điểm là có thể tìm được lời giải chấp nhận được với chi phí tính toán thấp. Do đó, cũng như các phương pháp heuristics, phương pháp này thường được sử dụng để xây dựng nghiệm ban đầu cho các phương pháp khác. CÁC PHƯƠNG PHÁP GIẢI BÀI TOÁN XẾP THỜI KHÓA BIỂU 2.3 Các phương pháp quy hoạch ràng buộc Bài toán xếp thời khóa biểu cũng có thể được mô hình hóa dưới dạng bài toán thỏa mãn ràng buộc (Constraint Satisfaction Problem) với các biến có miền xác định rời rạc và hữu hạn. Do đó, các hướng tiếp cận quy hoạch ràng buộc (Constraint Programming) có thể được áp dụng để giải quyết bài toán xếp thời khóa biểu.
Ưu điểm của các hướng tiếp cận này là khả năng tận dụng lại kết quả của các bài toán có mô hình biểu diễn tương tự. Các hướng tiếp cận tiêu biểu cho toán thời khóa biểu cũng sử dụng phương pháp quy hoạch ràng buộc được trình bày cụ thể trong các bài khảo sát của nhóm tác giả Edmund Burke [9] và Rong Qu [33].4 Các phương pháp metaheuristic Trong các thập niên gần đây, nhóm các phương pháp metaheuristics đang được quan tâm nghiên cứu rộng rãi [38]. Theo định nghĩa trên trang web của dự án Metaheuristics Network (http://www.org), được thực hiện từ năm 2000 đến 2004, metaheuristics là một cách gọi chung cho các phương pháp có thể được sử dụng để giải quyết nhiều loại bài toán tối ưu tổ hợp khó. Nói cách khác, một phương pháp metaheuristics có thể được xem như một khung thuật giải chung có thể được áp dụng để giải quyết các bài toán tối ưu hóa khác nhau với tương đối ít sửa đổi (cần thiết) để thích ứng với một bài toán cụ thể.
Theo Rhydian Lewis [27], các phương pháp metaheuristics giải bài toán thời khóa biểu có thể được chia thành 3 loại chính. Loại thứ nhất là các phương pháp một bậc (1-stage method), sử dụng một hàm mục tiêu chung cho cả ràng buộc cứng lẫn ràng buộc mềm. Loại thứ hai là các phương pháp hai bậc (2-stage method), chia việc xếp thời khóa biểu thành 2 giai đoạn. Trong đó, giai đoạn đầu tập trung xây dựng một thời khóa biểu không vi phạm bất kì ràng buộc cứng nào, giai đoạn thứ hai tập trung giảm thiểu các vi phạm ràng buộc mềm.
Loại thứ ba là các phương pháp nới lỏng, bước đầu xây dựng một thời khóa biểu có thể vi phạm một hoặc một số ràng buộc cứng, sau đó, tìm cách loại bỏ các vi phạm cho các ràng buộc cứng này và giảm thiểu các vi phạm cho ràng buộc mềm ở các bước tiếp theo. Trong ba loại phương pháp nói trên, các phương pháp 1-bậc có cách tiếp cận trực tiếp nhất. Với loại phương pháp này, các ràng buộc của bài toán được gán trọng số 15 CHƯƠNG 2. CÁC PHƯƠNG PHÁP GIẢI BÀI TOÁN XẾP THỜI KHÓA BIỂU khác nhau, tùy theo mức độ ưu tiên trong việc hạn chế các vi phạm của mỗi ràng buộc.
Theo đó, các ràng buộc cứng sẽ có trọng số cao hơn hẳn các ràng buộc mềm để có ảnh hưởng lớn hơn đến giá trị của hàm mục tiêu. Ví dụ, giả sử trọng số cho mỗi vi phạm ràng buộc mềm đều bằng nhau và bằng 1, còn trọng số của mỗi ràng buộc cứng được cho là 10000. Khi đó, nếu giá trị hàm mục tiêu nhỏ hơn 10000 thì thời khóa biểu đang xét không còn vi phạm ràng buộc cứng (với giả thiết số vi phạm ràng buộc mềm tối đa không thể vượt quá 10000). Như vậy, bằng việc giảm giá trị hàm mục tiêu trong quá trình tính toán, phương pháp 1-bậc có khả năng xây dựng được một thời khóa biểu không còn vi phạm ràng buộc cứng (thời khóa biểu chấp nhận được).
Các phương pháp 1-bậc có ưu điểm là dễ thực hiện và sửa đổi, tuy nhiên không hiệu quả khi áp dụng cho các bài toán phức tạp, có nhiều ràng buộc, bộ dữ liệu lớn,. Với bài toán có nhiều ràng buộc, có dữ liệu phức tạp, các phương pháp 2-bậc có thể cho nghiệm tốt hơn so với các phương pháp 1-bậc. Trong các phương pháp này, giai đoạn thứ nhất chỉ tập trung vào việc xây dựng thời khóa biểu không có vi phạm ràng buộc cứng, việc tính toán các vi phạm ràng buộc mềm được tạm thời bỏ qua. Như vậy, kết quả của giai đoạn này chính là một thời khóa biểu chấp nhận được.
Tuy nhiên, hiệu quả của các phương pháp này phụ thuộc vào việc có thể hay không xây dựng được một thời khóa biểu chấp nhận được trong thời gian hợp lý. Khác với các phương pháp 2-bậc, trong giai đoạn thứ nhất, các phương pháp nới lỏng cho phép thời khóa biểu đang xây dựng được vi phạm một hoặc một số ràng buộc nào đó (có thể là ràng buộc cứng). Ví dụ, nếu việc xếp một lớp học phần vào thời khóa biểu hiện tại có thể vi phạm một ràng buộc cứng nào đó thì việc xếp chỗ cho lớp học phần đó sẽ tạm thời bị bỏ qua hoặc tự động thêm vị trí mới (không nằm trong số các vị trí cho trước của thời khóa biểu) để xếp cho lớp học phần đó. Khi đó, các giá trị như số lớp học phần hoặc số tiết chưa được xếp lịch, số vị trí mới được thêm vào,.
sẽ được lưu lại. Trong quá trình sắp xếp sau đó, phương pháp sẽ tìm cách giảm các giá trị này cùng với giá trị của hàm mục tiêu.