Luận văn thạc sĩ: Nâng cao hiệu quả công tác xếp thời khóa biểu tại trường đại học Cần Thơ

Luận văn thạc sĩ nghiên cứu kỹ thuật công nghiệp đề xuất giải pháp cải thiện kết quả công tác xếp thời khóa biểu ứng dụng tại, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện

• Tác giả: Phạm Thị Bích Trâm
• Người hướng dẫn: TS. Lê Đức Đạo
• Trường học: Đại học Bách Khoa
• Chuyên ngành: Kỹ thuật công nghiệp
• Đề tài: Giải pháp nâng cao hiệu quả xếp thời khóa biểu tại trường đại học Cần Thơ
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2023
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• NHIỆM VỤ LUẬN VĂN THẠC SĨ
• LỜI CẢM ƠN
• TÓM TẮT LUẬN VĂN
• ABSTRACT
• LỜI CAM ĐOAN
• DANH MỤC BẢNG
• DANH MỤC HÌNH
• DANH MỤC VIẾT TẮT
• 1. CHƯƠNG 1: TỔNG QUAN
• 1.1. Tổng quan
• 1.2. Mục tiêu của đề tài
• 1.3. Đối tượng và phạm vi nghiên cứu
• 1.4. Phương pháp nghiên cứu
• 1.5. Cấu trúc của đề tài
• 1.6. Kế hoạch thực hiện
• 1.7. Phương pháp luận
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT VÀ LƯỢC KHẢO TÀI LIỆU
• 2.1. Giới thiệu về điều độ
• 2.2. Các phương pháp giải bài toán lập thời khóa biểu
• 2.3. Lý thuyết về giải thuật di truyền
• 2.3.1. Ứng dụng của giải thuật
• 2.4. Lược khảo tài liệu
• 3. CHƯƠNG 3: PHÂN TÍCH THỰC TRẠNG CÔNG TÁC XẾP THỜI KHOÁ BIỂU CỦA TRƯỜNG ĐẠI HỌC
• 3.1. Giới thiệu chung
• 3.2. Phân tích thực trạng công tác xếp thời khóa biểu tại Trường Đại học Kỹ thuật - Công nghệ Cần Thơ
• 3.2.1. Thực trạng công tác lập thời khóa biểu tại Trường Đại học Kỹ thuật - Công nghệ Cần Thơ
• 3.2.2. Đánh giá công tác xếp thời khóa biểu tại Trường Đại học Kỹ thuật - Công nghệ Cần Thơ
• 4. CHƯƠNG 4: ĐỀ XUẤT GIẢI PHÁP NÂNG CAO HIỆU QUẢ CÔNG TÁC LẬP THỜI KHOÁ BIỂU CHO TRƯỜNG ĐẠI HỌC
• 4.1. Chuẩn hóa quy trình lập thời khóa biểu cho trường đại học
• 4.2. Ứng dụng giải thuật di truyền để điều độ việc xếp thời khoá biểu cho Trường Đại học
• 4.2.1. Thiết lập mô hình bài toán điều độ thời khoá biểu
• 4.2.2. Áp dụng giải thuật di truyền vào bài toán lập thời khoá biểu
• 4.2.3. Phân tích kết quả điều độ
• 5. CHƯƠNG 5: KẾT LUẬN VÀ KIẾN NGHỊ
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu về thời khóa biểu

Thời khóa biểu đóng vai trò quan trọng trong việc tổ chức hoạt động giảng dạy tại các trường đại học. Nó không chỉ ảnh hưởng đến hiệu quả của việc giảng dạy mà còn tác động trực tiếp đến sự hài lòng của giảng viên và sinh viên. Việc lập thời khóa biểu một cách hợp lý giúp tối ưu hóa việc sử dụng nguồn lực và thời gian, từ đó nâng cao hiệu quả học tập. Các yếu tố cần xem xét trong quá trình lập thời khóa biểu bao gồm lịch học, sự phân bổ giảng viên, và cơ sở vật chất. Việc quản lý thời gian hiệu quả là điều cần thiết để đạt được mục tiêu giáo dục. Theo nghiên cứu, một thời khóa biểu tốt không chỉ giúp giảm thiểu xung đột về lịch trình mà còn tạo điều kiện thuận lợi cho sinh viên trong việc tham gia các lớp học.

1.1. Tầm quan trọng của thời khóa biểu

Việc xây dựng thời khóa biểu không chỉ đơn thuần là phân bổ thời gian mà còn là một nghệ thuật trong việc cân bằng các yếu tố khác nhau. Một thời khóa biểu hợp lý sẽ tạo ra môi trường học tập tích cực, nâng cao sự hài lòng của sinh viên và giảng viên. Theo một nghiên cứu gần đây, sự hài lòng của giảng viên với thời khóa biểu có thể ảnh hưởng đến chất lượng giảng dạy và sự gắn bó của họ với trường. Do đó, cần phải có những giải pháp hiệu quả để cải thiện quy trình lập thời khóa biểu, từ đó nâng cao hiệu quả công tác giảng dạy tại Trường Đại học Kỹ thuật - Công nghệ Cần Thơ.

II. Phân tích thực trạng công tác xếp thời khóa biểu

Đánh giá thực trạng công tác xếp thời khóa biểu tại Trường Đại học Kỹ thuật - Công nghệ Cần Thơ cho thấy nhiều vấn đề tồn tại trong quy trình hiện tại. Các giảng viên thường gặp khó khăn trong việc điều chỉnh lịch học do sự xung đột giữa các lớp học và sự hạn chế về cơ sở vật chất. Nghiên cứu sử dụng phương pháp khảo sát để thu thập ý kiến từ giảng viên về sự hài lòng và những vấn đề họ gặp phải trong quá trình giảng dạy. Kết quả cho thấy có một tỷ lệ lớn giảng viên không hài lòng với cách phân bổ thời gian hiện tại. Điều này cho thấy cần thiết phải có những giải pháp giáo dục cụ thể để cải thiện tình hình. Việc phân tích dữ liệu từ khảo sát giúp xác định rõ ràng các yếu tố ảnh hưởng đến việc lập thời khóa biểu, từ đó đưa ra những đề xuất hợp lý.

2.1. Đánh giá hiện trạng

Hiện trạng công tác xếp thời khóa biểu tại Trường Đại học Kỹ thuật - Công nghệ Cần Thơ cho thấy quy trình lập thời khóa biểu còn nhiều bất cập. Các giảng viên thường xuyên phải điều chỉnh lịch học do không có sự đồng bộ giữa các bộ môn và phòng học. Số liệu khảo sát cho thấy có tới 60% giảng viên cảm thấy không hài lòng với quy trình hiện tại. Điều này không chỉ ảnh hưởng đến hiệu quả giảng dạy mà còn làm giảm động lực làm việc của giảng viên. Sự thiếu hụt trong việc phân bổ thời gian và không gian học tập phù hợp là một trong những nguyên nhân chính dẫn đến tình trạng này. Cần có những giải pháp cụ thể để cải thiện quy trình lập thời khóa biểu nhằm nâng cao hiệu quả công tác giảng dạy.

III. Đề xuất giải pháp nâng cao hiệu quả công tác lập thời khóa biểu

Để nâng cao hiệu quả công tác lập thời khóa biểu, cần thiết phải chuẩn hóa quy trình lập lịch học. Việc ứng dụng giải thuật di truyền vào quá trình lập thời khóa biểu có thể giúp tối ưu hóa việc phân bổ thời gian và giảm thiểu xung đột giữa các lớp học. Giải pháp này không chỉ giúp tiết kiệm thời gian mà còn nâng cao chất lượng giảng dạy. Cụ thể, việc thu thập và phân tích dữ liệu học tập từ các học kỳ trước sẽ cung cấp thông tin quý giá để lập kế hoạch cho các học kỳ tiếp theo. Các giảng viên cũng nên được tham gia vào quá trình này để đảm bảo rằng thời khóa biểu đáp ứng nhu cầu giảng dạy của họ. Bằng cách này, có thể tạo ra một thời khóa biểu linh hoạt và hiệu quả hơn cho Trường Đại học Kỹ thuật - Công nghệ Cần Thơ.

3.1. Chuẩn hóa quy trình lập thời khóa biểu

Quy trình lập thời khóa biểu cần được chuẩn hóa để đảm bảo tính nhất quán và hiệu quả. Việc áp dụng các công nghệ mới, chẳng hạn như phần mềm hỗ trợ lập lịch, sẽ giúp giảm thiểu thời gian và công sức trong việc phân bổ thời gian học. Đồng thời, cần có một bộ tiêu chí rõ ràng để đánh giá hiệu quả của thời khóa biểu sau mỗi kỳ học. Việc thường xuyên khảo sát ý kiến giảng viên và sinh viên về thời khóa biểu cũng rất quan trọng để có thể điều chỉnh kịp thời và phù hợp với nhu cầu thực tế. Điều này sẽ góp phần nâng cao hiệu quả của công tác giảng dạy tại Trường Đại học Kỹ thuật - Công nghệ Cần Thơ.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh giáo dục đại học hiện đại, việc tối ưu hóa nguồn lực đào tạo đóng vai trò sống còn đối với chất lượng vận hành của các trường đại học. Tại Trường Đại học Kỹ thuật - Công nghệ Cần Thơ, với quy mô hơn 5.000 sinh viên phân bổ trên 22 chuyên ngành và 73 lớp học, áp lực quản lý giảng đường là rất lớn khi nhà trường chỉ có hơn 30 phòng học lý thuyết và 12 phòng thực hành. Công tác lập thời khóa biểu hiện nay đối mặt với thách thức tổ hợp khổng lồ, thuộc nhóm bài toán NP-hard điển hình khi một hệ thống 50 lớp học với 15 môn học và 30 tiết mỗi tuần có thể tạo ra không gian tìm kiếm lên đến hàng chục nghìn khả năng kết hợp.

Vấn đề nghiên cứu trọng tâm xuất phát từ việc quy trình xếp lịch thủ công hiện tại tốn nhiều thời gian, thường kéo dài từ 2 đến 3 tuần mỗi đầu học kỳ nhưng vẫn dẫn đến tình trạng phân bổ lịch giảng dạy bị phân tán, gây lãng phí công suất phòng học và làm suy giảm mức độ hài lòng của đội ngũ giảng viên. Mục tiêu cụ thể của luận văn là phân tích toàn diện thực trạng công tác điều độ thời khóa biểu, từ đó xây dựng mô hình toán học và ứng dụng Giải thuật Di truyền (Genetic Algorithm) nhằm tối ưu hóa việc phân bổ lịch giảng dạy và phòng học.

Nghiên cứu được triển khai thực nghiệm tại Khoa Kinh tế - Quản lý công nghiệp trong Học kỳ 1 năm học 2022 - 2023 với dữ liệu gồm 42 học phần tương đương 56 lớp học phần. Ý nghĩa thực tiễn của đề tài được đo lường qua việc giảm thời gian lập lịch từ 14 ngày làm việc xuống còn dưới 2 giờ tính toán tự động, đồng thời giảm khoảng 35% đến 38% số ngày lên lớp phân tán của giảng viên, góp phần nâng cao hiệu suất sử dụng cơ sở vật chất lên trên 85% và cải thiện rõ rệt mức độ hài lòng của cán bộ giảng dạy.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên ba trụ cột lý thuyết cốt lõi trong kỹ thuật hệ thống và tối ưu hóa tổ hợp:

Thứ nhất, Lý thuyết Điều độ trong sản xuất và dịch vụ (Scheduling Theory). Đây là quá trình ra quyết định nhằm phân phối tập hợp tài nguyên hữu hạn (gồm hơn 30 phòng học lý thuyết, 12 phòng thực hành và khung giờ 13 tiết mỗi ngày) cho các tác vụ giảng dạy cụ thể để đạt được các mục tiêu tối ưu như cực tiểu hóa thời gian chờ và cân bằng tải giảng dạy.

Thứ hai, Lý thuyết Tối ưu hóa tổ hợp và Phân loại bài toán NP-hard. Luận văn phân tích rõ các phương pháp giải truyền thống như vét cạn hay leo đồi (Hill Climbing) đều bộc lộ hạn chế lớn khi không gian trạng thái quá rộng hoặc dễ bị mắc kẹt tại điểm tối ưu cục bộ.

Thứ ba, Giải thuật Di truyền (Genetic Algorithm - GA) được lựa chọn làm nền tảng thuật toán chính. Mô hình này mô phỏng quá trình chọn lọc tự nhiên với các khái niệm chuyên ngành:

• Nhiễm sắc thể (Chromosome): Mỗi cá thể đại diện cho một phương án phân bổ thời khóa biểu hoàn chỉnh.
• Gen: Đại diện cho một sự kiện giảng dạy gồm mã môn học, giảng viên, lớp học phần, phòng học và khung thời gian.
• Quần thể (Population): Tập hợp các phương án xếp lịch được khởi tạo ngẫu nhiên nhưng thỏa mãn điều kiện tiên quyết.
• Hàm thích nghi (Fitness Function): Đo lường chất lượng của từng phương án dựa trên mức độ thỏa mãn hệ thống ràng buộc.
• Hệ thống ràng buộc: Được phân định chặt chẽ thành Ràng buộc cứng (tuyệt đối không trùng phòng, không trùng giờ của giảng viên và lớp học), Ràng buộc trung bình (ưu tiên phân bổ phòng phù hợp quy mô sĩ số), và Ràng buộc mềm (tập trung tiết dạy liền mạch, giảm số ngày lên lớp cho giảng viên).

Phương pháp nghiên cứu

Nghiên cứu kết hợp chặt chẽ giữa dữ liệu thứ cấp và dữ liệu sơ cấp nhằm đảm bảo tính khoa học:

• Dữ liệu thứ cấp: Thu thập toàn bộ kế hoạch phân công giảng dạy Học kỳ 1 năm học 2022 - 2023 tại Khoa Kinh tế - Quản lý công nghiệp với 42 học phần, danh mục 30 phòng học và thời gian biểu 13 tiết mỗi ngày (5 tiết sáng, 5 tiết chiều, 3 tiết tối).
• Dữ liệu sơ cấp: Khảo sát thực tế với cỡ mẫu gồm 72 cán bộ, giảng viên đang trực tiếp giảng dạy tại trường. Phương pháp chọn mẫu là chọn mẫu toàn bộ nhằm thu thập đầy đủ ý kiến phản hồi về thực trạng xếp lịch.

Lý do lựa chọn phương pháp phân tích: Tác giả sử dụng phương pháp thống kê mô tả, phân tích định lượng trên phần mềm bảng tính và sơ đồ nhân quả Ishikawa để bóc tách nguyên nhân gốc rễ. Giải thuật di truyền được lựa chọn để giải quyết bài toán vì GA là phương pháp tối ưu hóa toàn cục mạnh mẽ, có khả năng tìm kiếm đa điểm, không phụ thuộc vào đạo hàm hàm mục tiêu và xử lý xuất sắc các bài toán tổ hợp đa ràng buộc. Timeline nghiên cứu được thực hiện xuyên suốt trong 5 tháng, từ tháng 02/2023 đến tháng 06/2023 theo lộ trình: nghiên cứu lý thuyết (tháng 2), khảo sát thực trạng (tháng 3), thiết lập mô hình và thử nghiệm GA (tháng 4 - 5), và nghiệm thu đánh giá (tháng 6/2023).

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình khảo sát 72 cán bộ giảng viên và phân tích dữ liệu thực tế tại Khoa Kinh tế - Quản lý công nghiệp đã mang lại 4 phát hiện quan trọng:

Thứ nhất, mức độ không hài lòng về quy trình xếp lịch hiện tại chiếm tỷ lệ áp đảo. Có tới 50% giảng viên (36/72 người) không hài lòng với quy trình quản lý và vận hành công tác lập lịch; 24% giảng viên (17/72 người) phản ánh phương pháp xếp lịch thủ công thiếu tính tối ưu và thiếu công cụ kiểm soát tự động.

Thứ hai, tình trạng phân tán số ngày lên lớp diễn ra nghiêm trọng. Thống kê 16 giảng viên cơ hữu trong học kỳ khảo sát cho thấy số ngày lên lớp mỗi tuần gần như tương đương 1:1 với số lượng học phần phụ trách. Giảng viên dạy 4 đến 5 học phần phải đến trường 4 đến 5 ngày trong tuần, trong khi mỗi buổi chỉ dạy 2 hoặc 3 tiết. Có đến 56% giảng viên (40/72 người) bày tỏ mong muốn được bố trí dạy từ 2 học phần trở lên trong cùng một ngày để giảm bớt chi phí và thời gian đi lại.

Thứ ba, sự phân bổ tài nguyên phòng học chưa đạt hiệu suất cao. Mặc dù nhà trường có hơn 30 phòng lý thuyết nhưng lịch dạy bị dồn cục bộ vào các buổi sáng thứ Ba đến thứ Sáu, trong khi các buổi chiều và ngày thứ Bảy có tỷ lệ trống phòng lên đến hơn 25%, dẫn đến tình trạng vừa thiếu phòng cục bộ vừa lãng phí hạ tầng.

Thứ tư, khi đưa bộ dữ liệu 56 lớp học phần vào thử nghiệm với Giải thuật Di truyền, thuật toán đã giải quyết triệt để 100% các vi phạm ràng buộc cứng (hoàn toàn không có xung đột phòng hay trùng lịch giảng viên). Đồng thời, GA giúp giảm số ngày lên lớp trung bình của giảng viên từ 4,2 ngày/tuần xuống còn 2,6 ngày/tuần (mức giảm ấn tượng 38,1%), gom các tiết dạy thành các khối liền mạch khoa học.

Thảo luận kết quả

Nguyên nhân chính dẫn đến sự không hiệu quả của công tác xếp lịch được luận văn làm rõ thông qua Sơ đồ xương cá Ishikawa. Sự thiếu hiệu quả bắt nguồn từ 4 nhóm nguyên nhân: phương pháp thủ công dựa vào kinh nghiệm cá nhân, chưa có quy trình chuẩn hóa đồng bộ giữa Phòng Đào tạo và các Khoa, cơ sở vật chất giới hạn (hơn 30 phòng cho 73 lớp toàn trường), và việc chưa ứng dụng các giải thuật tối ưu hóa hiện đại.

Trong phần trình bày kết quả, dữ liệu được trực quan hóa rõ nét qua các dạng đồ thị:

• Biểu đồ tròn thể hiện cơ cấu các nguyên nhân gây không hài lòng, trong đó quy trình chiếm 50%, phương pháp chiếm 24%, tính linh hoạt chiếm 14%, tốc độ truyền tin chiếm 8% và lý do khác chiếm 4%.
• Biểu đồ cột kép so sánh tương quan giữa số lớp học phần và số ngày lên lớp thực tế của 16 giảng viên trước khi tối ưu, phản ánh rõ sự phân tán lịch dạy.
• Biểu đồ đường thể hiện sự chênh lệch rõ rệt về số ngày lên lớp của từng giảng viên trước và sau khi áp dụng giải thuật GA, minh chứng số ngày đến trường giảm từ 1 đến 2 ngày/tuần đối với mỗi cá nhân.

So sánh với các nghiên cứu tương tự trong và ngoài nước, kết quả này hoàn toàn tương thích với các nghiên cứu của các học giả quốc tế tại Đại học Alexandria khi áp dụng GA cho bài toán thời khóa biểu. Nghiên cứu khẳng định giải thuật di truyền vượt trội hơn hẳn phương pháp leo đồi và luyện kim (Simulated Annealing) trong việc cân bằng giữa tốc độ hội tụ và khả năng khám phá không gian tìm kiếm, giúp loại bỏ hoàn toàn bế tắc cục bộ trong bài toán lập lịch đào tạo.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu thực nghiệm, tác giả đề xuất hệ thống 4 giải pháp đồng bộ nhằm nâng cao hiệu quả công tác xếp thời khóa biểu:

Thứ nhất, chuẩn hóa quy trình lập thời khóa biểu 5 giai đoạn. Phòng Đào tạo phối hợp cùng Ban Giám hiệu ban hành quy chế phối hợp rõ ràng:

• Giai đoạn 1: Các Khoa hoàn tất kế hoạch phân công giảng dạy trước khi bắt đầu học kỳ 4 tuần.
• Giai đoạn 2: Phòng Đào tạo nhập dữ liệu và chạy thuật toán tối ưu hóa trong vòng 3 ngày làm việc.
• Giai đoạn 3: Công bố dự thảo thời khóa biểu cho giảng viên tự rà soát trong thời hạn 1 tuần.
• Giai đoạn 4: Hiệu chỉnh các phát sinh hợp lý trong 3 ngày.
• Giai đoạn 5: Cập nhật chính thức lên cổng thông tin sinh viên trước đợt đăng ký môn học 1 tuần. Mục tiêu giải pháp: Rút ngắn 60% tổng thời gian thực hiện quy trình và loại bỏ 100% sai sót do truyền đạt thông tin không chính thức qua mạng xã hội.

Thứ hai, phát triển và chuyển giao phần mềm lập lịch tự động ứng dụng Giải thuật Di truyền. Trung tâm Công nghệ Thông tin phối hợp cùng Bộ môn Kỹ thuật Hệ thống Công nghiệp đóng gói thuật toán GA thành module tích hợp trực tiếp vào hệ thống quản trị đại học (ERP). Cài đặt các tham số di truyền chuẩn hóa gồm: xác suất lai ghép từ 80% đến 90%, xác suất đột biến từ 1% đến 5%, kích thước quần thể từ 100 đến 200 cá thể. Mục tiêu giải pháp: Tạo ra phương án xếp lịch tối ưu chỉ trong 60 đến 120 phút xử lý máy tính.

Thứ ba, áp dụng nguyên tắc điều độ tập trung (Block Scheduling). Ban Chủ nhiệm các Khoa chuyên môn xây dựng kế hoạch phân công giảng viên dạy tối thiểu 2 học phần trong cùng một ngày làm việc đối với giảng viên phụ trách từ 2 lớp trở lên. Mục tiêu giải pháp: Giảm ít nhất 35% chi phí và thời gian di chuyển cho giảng viên, đồng thời tạo ra các ngày trống cố định trong tuần để phục vụ công tác nghiên cứu khoa học và sinh hoạt chuyên môn.

Thứ tư, nâng cấp và số hóa hạ tầng giảng đường. Phòng Quản trị Cơ sở vật chất lập kế hoạch đầu tư trung hạn trong 1 đến 2 năm tới nhằm trang bị hệ thống cảm biến điểm danh tự động và màn hình điện tử hiển thị trạng thái sử dụng của 30 phòng học theo thời gian thực. Mục tiêu giải pháp: Nâng công suất khai thác phòng học lên trên 85% và hỗ trợ điều phối phòng học linh hoạt khi có sự cố phát sinh.

Đối tượng nên tham khảo luận văn

Công trình nghiên cứu mang giá trị học thuật và thực tiễn cao, đặc biệt hữu ích cho 4 nhóm đối tượng sau:

Nhóm 1: Ban Giám hiệu và Lãnh đạo các trường Đại học, Cao đẳng. Luận văn cung cấp khung phương pháp luận khoa học và căn cứ định lượng để lãnh đạo nhà trường ra quyết định tái cấu trúc quy trình đào tạo, tối ưu hóa chi phí vận hành và phân bổ hiệu quả nguồn lực cơ sở vật chất trong điều kiện ngân sách và phòng ốc hạn chế.

Nhóm 2: Đội ngũ chuyên viên Phòng Đào tạo và Khảo thí. Đây là tài liệu hướng dẫn thực hành chi tiết giúp chuyên viên quản lý đào tạo chuyển đổi từ phương pháp xếp lịch thủ công sang quy trình tự động hóa chuyên nghiệp, nắm vững cách phân loại các hệ thống ràng buộc cứng - mềm để giảm thiểu áp lực công việc đầu mỗi học kỳ.

Nhóm 3: Giảng viên, học viên cao học và sinh viên chuyên ngành Kỹ thuật Công nghiệp, Hệ thống Thông tin Quản lý, Khoa học Máy tính. Luận văn là một case study thực tế xuất sắc về mô hình hóa toán học bài toán NP-hard, kỹ thuật mã hóa nhiễm sắc thể và phương pháp tinh chỉnh toán tử di truyền trong việc giải quyết bài toán tối ưu hóa tổ hợp đa mục tiêu.

Nhóm 4: Các doanh nghiệp và kỹ sư phát triển phần mềm giáo dục (EdTech). Tài liệu cung cấp logic nghiệp vụ sâu sắc, cấu trúc dữ liệu và thuật toán lõi giúp các nhà phát triển xây dựng các phân hệ xếp thời khóa biểu thông minh trong các gói phần mềm quản lý trường học hiện đại.

Câu hỏi thường gặp

Vì sao bài toán xếp thời khóa biểu đại học lại được xếp vào nhóm bài toán NP-hard? Bài toán thời khóa biểu là bài toán tối ưu hóa tổ hợp với không gian tìm kiếm bùng nổ theo cấp số nhân. Với một trường quy mô 50 lớp học, 15 môn và 30 tiết/tuần, số lượng phương án kết hợp là cực kỳ lớn. Không có thuật toán thời gian đa thức nào có thể tìm ra nghiệm tối ưu tuyệt đối trong mọi trường hợp, do đó phải sử dụng các giải thuật heuristic hoặc metaheuristic như GA để tìm lời giải gần tối ưu.

Giải thuật Di truyền có ưu điểm gì vượt trội so với các thuật toán tối ưu hóa truyền thống? Khác với phương pháp leo đồi chỉ tìm kiếm từ một điểm đơn lẻ và dễ rơi vào cực trị cục bộ, Giải thuật Di truyền làm việc trên một quần thể gồm hàng trăm cá thể (nghiệm tiềm năng) đồng thời. Thông qua các toán tử lai ghép và đột biến ngẫu nhiên có định hướng, GA có khả năng khám phá toàn diện không gian tìm kiếm, giúp tìm ra phương án tối ưu toàn cục nhanh chóng và chính xác.

Thuật toán GA xử lý thế nào khi có sự xung đột giữa các loại ràng buộc? Thuật toán xây dựng hàm thích nghi đa thành phần với hệ số phạt khác nhau. Ràng buộc cứng (như trùng phòng hoặc trùng giảng viên) được gán điểm phạt vô cùng lớn để loại bỏ ngay lập tức cá thể vi phạm trong quá trình chọn lọc. Ràng buộc mềm (như giảm số ngày lên lớp hoặc tránh tiết trống lẻ) được gán điểm phạt nhỏ hơn nhằm định hướng quần thể tiến dần đến phương án thuận tiện nhất cho người dạy và người học.

Mô hình trong luận văn có thể mở rộng áp dụng cho trường đại học có quy mô trên 10.000 sinh viên không? Hoàn toàn khả thi. Giải thuật Di truyền có tính mở rộng rất cao. Khi quy mô sinh viên tăng lên trên 10.000 người với hàng trăm phòng học, người quản trị chỉ cần tăng kích thước quần thể (từ 200 lên 500 cá thể) và điều chỉnh số thế hệ tiến hóa. Thuật toán vẫn đảm bảo hội tụ và đưa ra kết quả tối ưu trong khoảng thời gian chấp nhận được.

Lợi ích lớn nhất mà giải pháp mang lại cho đội ngũ giảng viên là gì? Lợi ích cốt lõi là tối ưu hóa quỹ thời gian. Khảo sát 72 giảng viên cho thấy 56% mong muốn dạy tập trung. Thuật toán GA đã giúp giảm trung bình 38,1% số ngày lên lớp mỗi tuần (từ 4,2 ngày xuống 2,6 ngày), giúp giảng viên giảm chi phí di chuyển, tập trung năng lượng cho từng buổi dạy và dành nhiều thời gian hơn cho nghiên cứu khoa học và phát triển chuyên môn.

Kết luận

• Luận văn đã phân tích toàn diện thực trạng công tác lập thời khóa biểu tại Trường Đại học Kỹ thuật - Công nghệ Cần Thơ, chỉ ra 50% giảng viên không hài lòng với quy trình thủ công hiện tại và 56% mong muốn được bố trí lịch dạy tập trung từ 2 học phần trở lên trong một ngày.
• Đề tài đã mô hình hóa thành công bài toán xếp lịch đại học phức tạp thành bài toán tối ưu hóa tổ hợp với hệ thống ràng buộc cứng, trung bình và mềm được định lượng rõ ràng.
• Ứng dụng thành công Giải thuật Di truyền (GA) trên bộ dữ liệu thực tế gồm 56 lớp học phần, loại bỏ hoàn toàn 100% xung đột lịch giảng dạy và phòng học, đồng thời cắt giảm số ngày lên lớp trung bình của giảng viên từ 4,2 ngày xuống 2,6 ngày mỗi tuần.
• Đề xuất quy trình chuẩn hóa 5 bước kết hợp với 4 nhóm giải pháp chiến lược về công nghệ, nhân sự và cơ sở vật chất nhằm nâng cao hiệu suất khai thác giảng đường lên trên 85%.
• Lộ trình triển khai tiếp theo được xác định trong 3 giai đoạn: chuẩn hóa dữ liệu đầu vào trong 1 tháng, thử nghiệm phần mềm tích hợp GA trong 2 tháng và tiến tới triển khai đồng bộ cho toàn bộ 22 chuyên ngành của nhà trường trong vòng 6 tháng.

Để hiện đại hóa công tác quản trị đại học và nâng cao chất lượng giảng dạy, việc áp dụng công nghệ tối ưu hóa vào điều độ thời khóa biểu là bước đi tất yếu. Các đơn vị giáo dục hãy chủ động liên hệ và tham khảo chi tiết công trình nghiên cứu này để nhanh chóng chuẩn hóa và số hóa quy trình quản lý đào tạo tại cơ sở của mình ngay hôm nay.

Trích đoạn nội dung tài liệu

Chương 1 trình bày lý do chọn đề tài, mục tiêu nghiên cứu, xác định đối tượng và phạm vi nghiên cứu, phương pháp và kế hoạch thực hiện đề tài, sơ đồ phương pháp luận và cấu trúc của đề tài. CƠ SỞ LÝ THUYẾT VÀ LƯỢT KHẢO TÀI LIỆU Cơ sở lý thuyết là hệ thống hóa các lý thuyết và quan điểm lý luận để làm luận điểm khoa học xuyên suốt cho đề tài nghiên cứu. Các lý thuyết về điều độ, các phương pháp giải bài toán lập thời khóa biểu, lý thuyết về giải thuật di truyền và phương pháp áp dụng giải thuật được trình bày tại Chương này để làm cơ sở cho việc vận dụng. Các tài liệu liên quan được lượt khảo để tổng quan về hướng nghiên cứu liên quan đến đề tài, điểm mới trong hướng nghiên cứu của đề tài.1 Giới thiệu về điều độ Điều độ là một quá trình ra quyết định đóng vai trò rất quan trọng trong hầu hết các hoạt động, các ngành công nghiệp sản xuất và dịch vụ.

Kỹ thuật điêu độ được sử dụng trong mua bán và sản xuất, trong vận chuyển và phân bố, trong xử lý thông tin và truyền thông [7]. Chức năng của điều độ trong một tổ chức là sử dụng các kỹ thuật toán học hay một số phương pháp định lượng khác để phân phối hợp lý các nguồn tài nguyên có hạn phục vụ công việc. Sự phân phối tài nguyên thích hợp sẽ cho phép tổ chức đạt được mục tiêu tối ưu mong muốn. Nguồn tài nguyên (resources) có thể là các máy móc trong phân xưởng, các đường băng trong sân bay, các công nhân ở các công trường xây dựng hay các đơn vị xử lý trong môi trường tính toán,… Các công việc (task) có thể là các sự vận hành trong các công xưởng, các lần cất cánh hay đáp xuống tại sân bay, các giai đoạn trong một dự án xây dựng hay các chương trình máy tính được thi hành tương ứng với các nguồn tài nguyên.

Mỗi công việc có thể có một mức độ ưu tiên, một thời gian có thể bắt đầu sớm nhất và một ngày tới hạn riêng biệt. Các mục tiêu trong điều độ sản xuất, có thể có nhiều dạng khác nhau, ví dụ như cực tiểu thời gian hoàn thành các công việc hay cực tiểu các công việc trễ hạn [7] Chức năng điều độ trong một hệ thống sản xuất hay một tổ chức dịch vụ phải tương tác với nhiều chức năng khác nhau. Các sự tương tác này thường thông qua 7 mạng máy tính, nhưng trong nhiều tình huống, sự tương tác giữa điều độ và các chức năng ra quyết định khác xảy ra tròn các buổi họp hay qua thư báo.2 Các phương pháp giải bài toán lập thời khóa biểu  Đối với phương pháp tiếp cận truyền thống, một số phương pháp để giải bài toán lập thời khóa biểu như sau: - Giải thuật vét cạn (tìm kiếm theo chiều rộng hoặc chiều sâu) về mặt nguyên tắc luôn tìm được nghiệm nếu bài toán có nghiệm. Nhưng trên thực tế, các bài toán thời khóa biểu không nên áp dụng phương pháp này, vì ta phải phát triển một không gian trạng thái cực lớn trước khi đi đến trạng thái đích.

Do các hạn chế về thời gian tính toán và dung lượng bộ nhớ, không cho phép ta thực hiện được. Chẳng hạn, với bài toán thời khóa biểu cho 50 lớp học, mỗi lớp có 15 môn học, mỗi lớp có 30 tiết mỗi tuần thi không gian tìm kiếm rất lớn là 50*15*30 trường hợp. Dễ nhận thấy rằng, nếu dùng phương pháp vét cạn thì thời gian chạy để tìm lời giải tối ưu rất lớn, khó chấp nhận được.