Chương 1 Tổng quan Lập lịch là vấn đề liên quan đến việc phân bổ thời gian tổ chức các sự kiện trong điều kiện cho trước, với mục tiêu là đưa ra được giải pháp dưới dạng một thời gian biểu [1]. Bài toán lập lịch là bài toán nhằm giải quyết vấn đề trên sao cho hạn chế tối đa chi phí và nguồn lực sử dụng mà vẫn thỏa mãn các ràng buộc đã đặt ra. Các ràng buộc có thể chia làm 2 loại: ràng buộc cứng và ràng buộc mềm. Ràng buộc cứng là các ràng buộc không thể vi phạm, còn ràng buộc mềm là các ràng buộc không nhất thiết phải tuân theo, nhưng đóng vai trò quan trọng trong việc đưa ra một giải pháp tốt.
Điều này có nghĩa là một giải pháp tốt phải đảm bảo không vi phạm bất cứ ràng buộc cứng nào và nên thỏa mãn càng nhiều ràng buộc mềm càng tốt. Bài toán lập lịch là bài toán thường gặp trong nhiều lĩnh vực của cuộc sống như: vận tải [2], quản lý [3], y tế [4], thể thao [5], và giáo dục [6]. Hiện nay có nhiều bài toán về lập lịch trong lĩnh vực giáo dục mà hầu như trường đại học nào cũng phải đối mặt, ví dụ như: lập lịch môn học, lập lịch học toàn khóa, lập lịch thi, lập lịch hội đồng đánh giá đề tài hay luận văn. Các bài toán này đòi hỏi những giải pháp áp dụng được trong thực tế sao cho tận dụng hợp lý các tài nguyên hữu hạn sẵn có mà vẫn đáp ứng được từng yêu cầu cụ thể.
Mặc dù các bài toán này đã được nghiên cứu trong nhiều năm, việc tìm ra giải pháp tối ưu vẫn còn là thách thức cho cộng đồng khoa học vì hầu hết các bài toán lập lịch đã được chứng minh là bài toán NP-hard [7]. Hơn nữa, không tồn tại một giải pháp chung vì mỗi trường hợp cụ thể khác nhau có những yêu cầu không giống nhau. Bài toán thành lập hội đồng luận văn Thành lập hội đồng luận văn là một trong các bài toán lập lịch thuộc lĩnh vực giáo dục, và được áp dụng ở phạm vi các trường đại học. Quá trình thành lập hội đồng luận văn bao gồm 3 tác vụ chính: quyết định các thành viên của hội đồng, sắp xếp phòng để tổ chức, và sắp xếp thời gian tổ chức.
Kết quả lập lịch cần thỏa mãn rất nhiều ràng buộc, chẳng hạn như: thời gian diễn ra đợt bảo vệ luận văn, thời gian tổ chức từng hội đồng, số thành viên hội đồng, yêu cầu chuyên môn của thành viên 9 hội đồng, mọi hội đồng đều phải có sự tham gia của giảng viên ngoài trường (chi tiết các ràng buộc sẽ được trình bày ở chương sau). Bài toán thành lập hội đồng luận văn là một trong các bài toán cần giải quyết trong lĩnh vực giáo dục. Mặc dù nguồn tài nguyên về con người (giảng viên), phòng tổ chức có hạn, số lượng đề tài luận văn cần được đánh giá lại tăng lên hàng năm. Hơn nữa, các hội đồng đánh giá luận văn cần được tổ chức trong một khoảng thời gian hạn chế.
Những yếu tố này dẫn đến việc lập lịch hội đồng luận văn (bằng thủ công hay thậm chí tự động) đòi hỏi nhiều thời gian, công sức. Hơn thế nữa, về mặt lý thuyết, bài toán này đã được chứng minh là bài toán thuộc nhóm NP-hard [8]. Chính vì vậy, một giải pháp lập lịch hiệu quả vừa khả thi vừa có thể tiết kiệm thời gian cũng như chi phí là một nhu cầu rất cần thiết hiện nay. Luận văn này nhằm đề xuất giải pháp khả thi cho việc thành lập hội đồng luận văn đồng thời hướng đến giải quyết ba mục tiêu chính: (1) Giảm thiểu số buổi các giảng viên phải tham gia hội đồng; (2) Sắp xếp các hội đồng một cách liên tục nhất có thể; và (3) Hạn chế tối đa số phòng cần sử dụng.
Ngoài ra, với mục tiêu có thể triển khai giải pháp trong thực tế, một ứng dụng hỗ trợ lập lịch hội đồng có giao diện thân thiện người dùng được phát triển dựa trên giải pháp đề xuất. Tình hình nghiên cứu Hiện nay, nhiều giải pháp áp dụng cho bài toán lập lịch trong lĩnh vực giáo dục nói chung đã được đề xuất. Có thể chia các giải pháp này theo hai hướng tiếp cận chính: phương pháp chính xác (exact method) và phương pháp không chính xác (heuristic or meta-heuristic). Đối với các phương pháp chính xác, Bakir và Aksop [9] đề xuất mô hình quy hoạch nguyên 0-1 cho bài toán lập lịch ở trường đại học.
Phương pháp đề xuất sử dụng solver dựa trên mô hình này có thể tìm được giải pháp khả thi dễ dàng, nhưng không thể tìm được giải pháp tối ưu trong thời gian chấp nhận được. Cũng giải quyết cho bài toán lập lịch giảng dạy cho trường đại học, Daskalaki và cộng sự [10] đề xuất mô hình quy hoạch nguyên trong đó sử dụng hệ số chi phí (cost coefficient) để giảm thiểu không gian nghiệm và khiến bài toán dễ giải quyết hơn. Trong khi đó, một giải pháp sử dụng kỹ thuật branch and cut [11] được đề xuất bởi Burke và cộng sự nhằm lập lịch giảng dạy cho trường hợp cụ thể tại đại học Udine. Ngoài ra, cũng thuộc nhóm phương pháp này, một giải pháp sử dụng kỹ thuật cutting plane [12] và hiện thực bởi solver được Avella và cộng sự đề xuất nhằm tìm được giải pháp tối ưu.
10 Trong trường hợp bài toán tồn tại nghiệm tối ưu, phương pháp chính xác có ưu điểm là có thể tìn được nghiệm này nếu có đủ thời gian thực thi. Tuy nhiên, các bài toán thực tế thường có không gian nghiệm rất lớn (như đã trình bày ở trên, nhóm bài toán này thuộc nhóm NP-hard) dẫn đến việc rất khó để tìm được giải pháp tối ưu trong thời gian chấp nhận được khi sử dụng phương pháp chính xác. Điều này được thể hiện rất rõ trong các giải pháp thuộc nhóm chính xác ở trên. Hầu hết các giải pháp này chỉ dừng lại ở việc tìm giải pháp khả thi và có giá trị nghiệm tốt nhất có thể.
Mặc dù vậy, các giải pháp sử dụng solver này đòi hỏi thời gian thực thi lớn. Vì vậy, phần lớn các giải pháp hiện nay là sử dụng phương pháp không chính xác. Đặc điểm của phương pháp không chính xác là có thể giúp tìm ra lời giải trong khoảng thời gian chấp nhận được. Chất lượng của lời giải còn phụ thuộc vào cách phân tích bài toán và thuật toán sử dụng.
Nhóm thuật toán này được gọi là thuật toán heuristic hay thuật toán meta-heuristic. Một số thuật toán thường được dùng cho các bài toán lập lịch như: Thuật toán di truyền (Genetic algorithm), thuật toán memetic, thuật toán luyện kim (Annealing algorithm), thuật toán tabu (tabu search), thuật toán tìm cục bộ (local search). Nhiều phương pháp lập lịch hiện nay dựa trên heuristic hay meta-heuristic. Nhóm nghiên cứu của Aldy [13] đề xuất một heuristic để giải cùng lúc bài toán lập lịch dạy của giáo viên và bài toán lập lịch môn học.
Yang và Jat [14] sử dụng giải thuật di truyền có định hướng với hàm mục tiêu là giảm tối đa tổng số ràng buộc vi phạm (cả ràng buộc cứng và ràng buộc mềm). Nghiên cứu này dùng 3 toán tử lân cận (neighborhood operator) gồm di chuyển sự kiện sang thời điểm khác, hoán đổi thời gian tổ chức của hai sự kiện cho nhau và sắp xếp từng nhóm 3 sự kiện sao cho khác với trật tự ban đầu. Một số kỹ thuật meta-heuristic khác cũng được áp dụng thành công cho các bài toán lập lịch giáo dục, như giải thuật luyện kim [15], tabu search [16],[17], giải thuật memetic [18]. Các giải pháp đưa ra bởi nhóm thuật toán meta-heuristic thường có chất lượng khá tốt và thời gian xử lý có thể chấp nhận được.
Một nghiên cứu gần đây do nhóm của Masri [19] thực hiện cũng tập trung xử lý bài toán lập lịch hội đồng luận văn trong đó sử dụng thuật toán tham lam để thiết kế thời gian biểu tổ chức các hội đồng. Heuristic đề xuất trong nghiên cứu này có thời gian thực thi ngắn, nhưng chỉ quan tâm đến vấn đề tìm ra một giải pháp khả thi thỏa mãn các yêu cầu ràng buộc của Khoa Khoa Học Thông Tin thuộc trường đại học Kebangsaan của Malaysia, mà không bao gồm bất cứ nỗ lực tìm kiếm giải pháp tối ưu nào. Một nghiên cứu khác cũng được áp dụng cho việc lập lịch hồi đồng luận văn ở Việt Nam do Huynh và cộng sự [8] đề xuất sử dụng phương pháp di truyền để tìm giải pháp khả thi và đáp ứng các mục tiêu khác nhau. Trong luận văn này, một phương pháp dựa trên memetic được đề xuất nhằm lập lịch hội đồng luận văn thạc sĩ, áp dụng cho ngữ cảnh ở Việt Nam, vốn có sự khác 11 biệt về ràng buộc của bài toán so với công trình của Masri đã công bố.
Bên cạnh đó, ngoài sự khác biệt về phương pháp, luận văn này tập trung giải quyết các mục tiêu khác so với nghiên cứu của Huynh và cộng sự [8]. 12 Chương 2 Cơ sở lý thuyết Chương này trình bày những lý nền tảng sử dụng trong giải pháp được đề xuất trong luận văn này, bao gồm: heuristic, meta-heuristics, giải thuật di truyền, và giải thuật memetic. Heuristic Heuristic là khái niệm được dùng để nói đến các phương pháp được đề xuất dựa trên kinh nghiệm của con người nhằm giải quyết một vấn đề cụ thể. Một phương pháp heuristic tốt là phương pháp có thể đưa ra một giải pháp đủ tốt trong thời gian chấp nhận được.
Đối với các bài toán thuộc nhóm NP-hard vốn không thể tìm được lời giải tối ưu trong thời gian tuyến tính, phương pháp sử dụng heuristic là một cách giải quyết hiệu quả hiện nay. Khái niệm và đặc trưng Meta-heuristic được xem là kỹ thuật ở mức cao (high-level strategies) nhằm định hướng cho việc tìm nghiệm của một heuristic cụ thể. Một meta-heuristic được thiết kế nhằm tìm và tạo ra, hoặc chọn một heuristic có khả năng đưa ra giải pháp tốt hướng đến mục tiêu tìm ra giải pháp tối ưu. Meta-heuristic đặc biệt hiệu quả trong trường hợp thiếu thông tin, hoặc thông tin không hoàn chỉnh về không gian nghiệm, hoặc bị hạn chế về khả năng tính toán.
So sánh với giải thuật tối ưu và phương pháp lặp, meta-heuristic không đảm bảo lúc nào cũng có thể đưa ra giải pháp tối ưu toàn cục. Đa số các meta-heuristic đều hàm chứa một dạng nào đó của tối ưu ngẫu nhiên. Do đó giải pháp đưa ra bị ảnh hưởng bởi tập các biến được khởi tạo ngẫu nhiên.