Đề xuất giải thuật di truyền giải bài toán xếp thời khóa biểu

Bài viết đề xuất sử dụng giải thuật di truyền để giải bài toán xếp thời khóa biểu trường phổ thông, một loại bài toán xếp thời khóa biểu phổ biến. Nghiên cứu đã cài đặt và thí nghiệm giải thuật đề xuất trên một số bộ dữ liệu thực tế.
Nội dung trích xuất từ tài liệu:
Đề xuất giải thuật di truyền giải bài toán xếp thời khóa biểu TRƯỜNG ĐẠI HỌC SÀI GÒN SAIGON UNIVERSITY TẠP CHÍ KHOA HỌC SCIENTIFIC JOURNAL ĐẠI HỌC SÀI GÒN OF SAIGON UNIVERSITY Số 71 (05/2020) No. 71 (05/2020) Email: tcdhsg@sgu.edu.vn ; Website: http://sj.sgu.edu.vn/ ĐỀ XUẤT GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN XẾP THỜI KHÓA BIỂU Proposing a genetic algorithm to solve timetabling problem Nguyễn Hồ Thiên Đăng(1), Nguyễn Thị Hồng Bích(2), Thái Minh Tân(3), TS. Phan Tấn Quốc(4) (1)Học viên cao học Trường Đại học Sài Gòn (2) Trường THPT Ngô Quyền, Q.7, TP.HCM (3)Công ty TMA Solutions, TP.HCM (4) Trường Đại học Sài Gòn TÓM TẮT Việc xếp thời khóa biểu hợp lý là bài toán tối ưu có nhiều ứng dụng trong thực tế. Được phân loại thuộc lớp NP-complete và đã được nghiên cứu rộng rãi trong hàng chục năm qua với các hướng tiếp cận như quy hoạch toán học, tối ưu dựa trên ràng buộc, tối ưu đa mục tiêu, giải thuật tham lam, giải thuật metaheuristic.v.v. Nghiên cứu này đề xuất sử dụng giải thuật di truyền để giải bài toán xếp thời khóa biểu trường phổ thông, một loại bài toán xếp thời khóa biểu phổ biến. Nghiên cứu đã cài đặt và thí nghiệm giải thuật đề xuất trên một số bộ dữ liệu thực tế. Kết quả thực nghiệm cho thấy giải thuật đề xuất cho kết quả tốt hơn một số phần mềm hỗ trợ xếp thời khóa biểu cho các trường phổ thông hiện nay trên dựa trên trọng số một số ràng buộc của bài toán. Từ khóa: thời khóa biểu, thời khóa biểu trường phổ thông, giải thuật di truyền ABSTRACT Timetabling problem is optimization problems that have many practical applications; this is the problem of class NP-complete. Timetabling problem has been widely studied over the past decades with approaches such as mathematical programming, constraint-based approaches, multiobjective optimization, greedy algorithms, metaheuristic algorithms, etc. In this study, we propose a genetic algorithm to solve a form of Timetabling problem that is the School Timetabling problem. The proposed algorithm was conducted on some real data sets. Experimental results claim that our algorithm results in better results than some of the current school Timetabling software based on some constraints of the problem. Keywords: genetic algorithm, timetabling problem, school timetabling 1. Giới thiệu định (thường là theo tuần) sao cho thỏa Bài toán xếp thời khóa biểu trường học mãn được nhiều ràng buộc nhất có thể của (timetabling problem) là tạo ra một lịch bài toán. Bài toán xếp thời khóa biểu thuộc phân công giảng dạy giữa người dạy và lớp bài toán tối ưu NP-complete [1]. người học trong một chu kỳ thời gian cố Bài toán xếp thời khóa biểu được biết Email: quocpt@sgu.edu.vn 87 SCIENTIFIC JOURNAL OF SAIGON UNIVERSITY No. 71 (05/2020) đến rộng rãi với 3 dạng sau: bài toán xếp của lớp đó; các giáo viên có thể dạy môn thời khóa biểu trường phổ thông (school học ngoài chuyên môn chính, gọi là công timetabling-STTP); bài toán xếp thời khóa tác kiêm nhiệm. biểu trường đại học (course timetabling- Lớp học: lớp học gồm tập các học CTTP); bài toán xếp lịch thi (examination sinh học chung với nhau ở tất cả các môn timetabling-ETTP) [1]. học. Đã có nhiều công trình nghiên cứu về Phạm vi bài toán xếp thời khóa biểu đề bài toán xếp thời khóa biểu dựa trên các cập trong nghiên cứu này là các khối lớp hướng tiếp cận như giải thuật tô màu đồ thị, 10, 11 và 12. tiếp cận dựa trên ràng buộc, quy hoạch toán Phòng học: với bài toán xếp thời khóa học, tối ưu đa mục tiêu, giải thuật tham lam biểu ở trường phổ thông, mỗi lớp được cấp [2], giải thuật metaheuristic [3], [4], [5], cố định một phòng học lý thuyết trong suốt [6], [7]. năm học; mỗi phòng học có thêm thông tin Trong nghiên cứu này, chúng tôi đề là phòng học lý thuyết hay phòng thực xuất một giải thuật metaheuristic dạng hành, thực nghiệm. quần thể là giải thuật di truyền để giải bài Môn học: có thể gọi là môn, mỗi khối toán xếp thời khóa biểu trường phổ thông lớp trong một học kỳ có từ 13 đến 17 môn; với hy vọng có thể khắc phục được bẩy tối Môn ngữ văn, thể dục, quốc phòng phải ưu cục bộ so với các metaheuristic dạng cá xếp tiết cặp và không xếp tiết 2-3 vì sau t ...