Chương 1: MO DAU 1.1 Hiện trạng và khó khăn thực tế Việc xếp lịch thi là một vấn đề phức tạp và quan trọng mà nhiều trường học phải thực hiện ở mỗi học kỳ. Xếp lịch thi cần phải tìm kiếm một cách tốt nhất đề tô chức các kỳ thi cho hàng ngàn sinh viên trong một thời gian ngắn và trong những điều kiện hạn chế về tài nguyên. Đối với bài toán như này chúng ta cần phải tìm ra một giải pháp dé tối ưu về mặt thời gian, chi phí và tài nguyên. Tuy nhiên, mỗi phương pháp thường chi được đề xuất dựa trên một đơn vị trường học cụ thé và rất khó dé áp dụng cho những đơn vị khác.
Đối với khoa CNTT trường Đại học Nông Lâm TP.HCM hiện tại có một số van đề khó khăn trong một số học kỳ gần đây như sau: Một sinh thi nhiều hơn 1 môn trong cùng một ngày, sắp xếp ca thi không hợp lý (ca 1 tổ chức thi 4 phòng (8 cán bộ coi thi), ca 2 thi 2 phòng (4 cán bộ coi thi), ca 3 thi 5 phòng (10 can bộ coi thi), v.Dưới đây là các van đề của lịch thi học kỳ 1 năm 2021-2022: e Lịch thi của khóa 2019 từng gặp phải trường hợp thi 2 môn “quản trị mang” và Học ky 1 Năm học 2022-2023 Thời khóa biểu cá nhân. 8n 214483 Thương mại điện từ 01 3 DH19DTC 0 0 K.Châu 29/08/22 đến 13/11/22 214483 Thương mại điện từ 01-01 3 ere 0 0 K.H Châu 08/09/22 đến 13/11/22 214485 Data Mining 01 4 ĐANG 0 0 T.Việt 29/08/22 đến 18/12/22 214485 Data Mining 01-01 4 pH DH19DTB 0 0 T.Việt 05/09/22 đến 13/11/22 Hình 1.1: Lịch thi của một sinh viên khoa công nghệ thông tin đại học Nông Lâm e Lịch thi bị vấn đề ở môn thi van đáp (.NET) không đủ thời gian, chỉ có 6 tiết để báo cáo sau đó nhường phòng cho môn khác (Nhập môn tin học) vào thi. 66 or Lập trình .NET pen ren SA len Hút Mười túi 138|15/07/2022 | 1|P3 07g30 |! 67| 214201 [Nhập môn tin học 001_DH21DTA_20 xắn cr) hệ E3 sieon 30|15/07/2022 4|P4 loog4s 68| 214201 [Nhập môn tin học 002_DH21DTA_20 ae an Me oa Tang 30|15/07/2022 4|P2 0z4s |I 69| 214201 [Nhập môn tin học 003_DH21DTA_20 nà cr) lệ = a 31|15/07/2022 4|Pl og4s |I 70| 214201 [Nhập môn tin học o01_DH21DTD_0o1 [1915 1015(TH) le [Võ Tan Linh(TH) 30|15/07/2022 1|P4 12g15 Hình 1.2: Lịch thi bi trùng phòng thi Ngoài ra còn một số khó khăn trong việc xếp lịch thi là số lượng sinh viên qua lớn. Khi có quá nhiều sinh viên, việc sắp xếp một lịch thi phù hợp với tài nguyên hiện có( phòng học, thời gian, cán bộ coi thi, .) trở nên rất khó khăn.
Điều này cần phải được giải quyết bằng việc tìm kiếm một số phương án khác nhau và lựa chọn những giải pháp tốt nhất. Không chi vậy, khi sắp xếp lich thi, người quan lý cần cân nhắc nhiều yếu t6, bao gồm số lượng sinh viên, giảng viên, phòng thi, thời gian thi và các yêu cầu khác của các bộ phận liên quan. Lịch thi cần được tối ưu hóa để giảm thiểu số lần thi của sinh viên và tôi đa hóa sự linh hoạt trong việc sắp xếp thời gian cho các kỳ thi. Tuy nhiên, việc tối ưu hóa lịch thi sẽ làm cho quá trình sắp xếp lich thi trở nên phức tạp hơn.
Do đó vấn đề đặt ra là cần xây dựng một lịch thi thỏa mãn tất cả các ràng buộc trên đồng thời khai thác hiệu quả các nguồn tài nguyên. Bài toán xếp lịch thi thuộc lớp các bài toán NP-complete vì vậy có thé không tìm ra được lời giải tối ưu. Day là một bài toán không mới và đã có nhiều thuật toán được đưa ra dé giải quyết như thuật toán leo đổi, thuật toán luyện thép, thuật toán tô màu đồ thị, thuật toán đi truyén,. Tuy nhiên các thuật toán này thường không có tinh tổng quát và chi áp dung hiệu qua đối với các trường học có quy mô nhỏ, ít ràng buộc về mặt dữ liệu.2 Lý do chọn đề tài Như đã đề cập ở trên, bài toán xếp lịch thi là một trong những vấn đề quan trọng của mỗi cơ sở giáo dục.
Đề đạt được kết quả thi tốt, việc sắp xếp lịch thi phải được thực hiện kỹ lưỡng và đảm bảo tính công bằng cho tất cả sinh viên. Các trường học thường phải đối mặt với các thách thức khi sắp xếp lịch thi, bao gồm: e Số lượng sinh viên thi quá đông e Số lượng phòng thi hạn chế e Thời gian thi có giới han e Số lượng cán bộ coi thi không đủ Đề đảm bảo tính công bằng cho tắt cả sinh viên, việc sắp xếp lịch thi cần được thực hiện đúng cách và kỹ lưỡng. Đề giải quyết những khó khăn này, các phương pháp toán học và công nghệ thông tin hiện đại, như thuật toán di truyền, phỏng luyện kim,. đã được ứng dụng dé giúp sắp xếp lịch thi dễ dàng hơn.
Việc nghiên cứu và giải quyết vấn đề sắp xếp lịch thi không chỉ giúp cho việc quan lý và giảng day được tốt hon, mà còn giúp cho sinh viên dat được kết quả thi tốt hơn. Chính vì vậy, chọn đề tài "Sắp xếp lịch thi" là một lựa chọn hợp lý và có ý nghĩa thiết thực trong việc nâng cao chất lượng giáo dục và đảo tạo. Tóm lại bài toán lập lịch là một trong những van đề được quan tâm hàng đầu ở các trường đại học, cao dang. Cac céng viéc lién quan dén lập lich có thể kể đến như xếp thời khóa biểu, xếp lịch thi, xếp lịch thực hành,.
Day là việc bố trí các lớp môn học, phòng học, giảng viên, sinh viên, v. sao cho tất cả các ràng buộc cứng đều được thỏa mãn và thỏa mãn càng nhiều ràng buộc mềm càng tốt. Cho đến nay, đã có rất nhiều cách tiếp cận đã được đề xuất để giải quyết bài toán này ví dụ như thuật toán GA(Gao et al., 2007), PSO(Abayomi-Alli et al., 2019; Chu et al., 2006; Montero et al., 2011), SA(Aycan & Ayav, 2009; Basir et al., 2013; Goh et al. Tuy nhién, mỗi phương pháp thường chi được đề xuất dựa trên một don vị trường hoc cụ thé và rất khó dé áp dụng cho những đơn vị khác.
Vì những van đề trên nhóm đã đề xuất dùng thuật toán tối ưu phỏng theo cách săn mỗi của đàn sói xám dé giải quyết bài toán xếp lịch thi nhằm nâng cao chất lượng lời giải: thỏa mãn ràng buộc cứng và đạt được nhiêu rang buộc mêm càng tot. Mục tiêu đề tài e Muc tiêu tổng quát: - __ Nghiên cứu áp dụng thuật toán tôi ưu đàn sói xám dé xây dựng chương trình xếp lịch thi áp dụng cho khoa Công nghệ Thông tin, trường Đại học Nông Lâm TP. e Mục tiêu cu thể: - _ Nghiên cứu lý thuyết thuật toán GWO. - Ung dụng thuật toán GWO cho bài toán lập lich nhằm dé nâng cao hiệu suất của thuật toán (thời gian thực thi, tài nguyên, .) - So sánh kết quả thực nghiệm giữa thuật toán GWO và các thuật toán SA, GA với dữ liệu xếp lịch thi tại khoa CNTT, trường Đại học Nông Lâm Tp.
- _ Xây dựng chương trình xếp lịch thi trên nền tang web sử dụng các công nghệ: Spring Boot, ReactJs với các chức năng cơ bản dành cho sinh viên, giảng viên và nhân viên xép lịch thi.4 Nội dung nghiên cứu Nghiên cứu các đặc điểm đặc trưng của thuật toán GWO các thành phần cơ bản của thuật toán GWO như khởi tạo quan thé ban đầu, đánh giá độ thích nghỉ, các hành vi của sói xám (bao vây, săn môi, tân công). Bài toán sắp xếp lịch thi sử dụng thuật toán GWO trên nền tảng server Spring Boot và giao điện được sử dụng là ReactJs, giúp người dùng có thé thao tác trực tiếp và sắp xếp lịch thi theo dữ liệu đưa vào.5 Phạm vi nghiên cứu Với bài toán xếp lịch thi nhóm nghiên cứu và áp dụng ở khoa CNTT trường đại học Nông Lâm TP. Xếp lịch thi dựa trên dữ liệu lịch thi trong học kỳ của khoa và thông tin về phòng học của trường. Sau đó, dựa trên kết quả xếp lich thi các khoa chiu trách nhiệm phân công cán bộ coi thi cho các ca thi đã lên lịch.6 Cơ sở khoa học và thực tiễn Cơ sở khoa học của đề tài là dựa trên lý thuyết về tối ưu hóa tổ hợp, thuật toán, toán học ứng dụng và công nghệ thông tin.
Các kiến thức về tối ưu hóa tô hợp, thuật toán và toán học ứng dụng là cơ sở lý thuyết quan trọng để giải quyết các bài toán phức tạp, trong đó bao gồm cả bài toán sắp xếp lịch thi. Cuối cùng nhóm đã hướng đến thuật toán GWO dé tập trung nghiên cứu và ứng dụng vào đề tài sắp lich thi cho khoa CNTT trường đại học Nông Lâm TP. Ngoài ra, đề tài cũng sử dụng các kiến thức về cấu trúc đữ liệu, thuật toán sắp xếp, thuật toán tìm kiếm và các kỹ thuật lập trình hiện đại như ReactJs, Redux, Redux- Saga dé thiết kế và xây dựng hệ thống sắp xếp lịch thi. Thực tế, bài toán sắp xếp lịch thi là một bài toán phức tạp và thường xuyên được áp dụng trong nhiều lĩnh vực khác nhau, đặc biệt là trong giáo dục.
Việc sắp xếp lịch thi có thể giúp cho việc tô chức ky thi, học kỳ, niên khóa được hiệu quả hơn, giảm thiểu thời gian và chi phí tổ chức, đồng thời giúp cho giảng viên và sinh viên có thời gian giảng dạy và học tập hợp lý hơn. Với mục tiêu đó, dé tài "Sắp xếp lịch thi" cung cấp cho người sử dụng giải pháp tối ưu dé sắp xếp lich thi một cách nhanh chóng, chính xác và đáp ứng nhu cầu của người dùng. Hệ thống cũng được thiết kế dé có thé mở rộng và sử dụng cho nhiều mô hình và kịch bản khác nhau trong thực tế. 17 Sản phẩm e Sau quá trình xây dựng phần mềm hỗ trợ sắp xếp lịch thi, sản phẩm đã được hoàn thành và đáp ứng tốt các yêu cầu và mục tiêu đề ra.
Sản phẩm này có thé giúp cho các trường trong việc quản lý và sắp xếp lịch thi một cách nhanh chóng và hiệu quả hơn. e Phần mềm được phát triển trên nền tảng web, sử dung các công nghệ như ReactJs, Redux, Redux Saga, Spring Boot và MySQL. Với giao diện thân thiện, trực quan, dễ sử dụng, sản phẩm giúp cho việc sắp xếp lịch thi trở nên đơn giản hơn. Ngoài ra, sản phẩm còn tích hợp các tính năng xem điểm thi, xem thời khóa biéu hỗ trợ cho sinh viên hiệu quả hơn.