tailieunhanh - Đề 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ế. | 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@ Website http ĐỀ 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 3 Công ty TMA Solutions 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 . 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 .