- VÀO BÀI TOÁN QUẢN LÝ XẾP LỊCH THI KẾT THÚC CÁC LỚP HỌC PHẦN TẠI TRƯỜNG ĐẠI HỌC CẦN THƠ. - Mục tiêu của bài viết là đề xuất quy trình và xây dựng hệ thống quản lý công tác tổ chức thi kết thúc các lớp học phần tại Trường Đại học Cần Thơ. - Bài viết tập trung vào việc đề xuất quy trình đăng ký xếp lịch thi chung và thi riêng nhằm giải quyết các vấn đề bất cập còn tồn tại của việc tổ chức một tuần thi riêng và một tuần thi chung. - Từ quy trình đề xuất, chúng tôi xây dựng hệ thống cho phép giảng viên đăng ký lịch thi riêng và thi chung một cách thuận lợi trong đó lịch thi chung được xếp một cách tự động theo tiêu chí không có sinh viên bị trùng lịch thi và không thi cùng hai môn thi trong một buổi thi.. - Giải thuật xếp thời khóa biểu ứng dụng vào bài toán quản lý xếp lịch thi kết thúc các lớp học phần tại Trường Đại học Cần Thơ. - Một trong số những hoạt động vẫn đang được thực hiện thủ công đó là công tác tổ chức thi kết thúc các lớp học phần. - Trường Đại học Cần Thơ giành riêng 2 tuần tại mỗi học kỳ để các khoa tổ chức thi cuối kỳ cho các lớp học phần trong đó bao gồm: 1 tuần thi riêng (giảng viên tự tổ chức thi theo thời khóa biểu của lớp học phần), 1 tuần thi chung (giáo vụ khoa thực. - hiện xếp lịch thi và bố trí cán bộ coi thi). - Cách tổ chức như thế này tuy có thể giải quyết vấn nạn trùng lịch thi nhưng vẫn có nhiều bất cập mà đặc biệt là tạo sức ép rất lớn nơi người học. - Trên phạm vi thế giới, đa phần các trường đại học đều tổ chức đào tạo theo học chế tín chỉ tuy nhiên họ lại tổ chức thi tập trung, trong đó các khoa quản lý đào tạo sẽ thực hiện nhiệm vụ xếp lịch thi cho tất cả các lớp học phần có mở ở một học kỳ cụ thể trong khoảng thời gian nhất định.. - Lịch thi của các lớp học phần do một khoa đào tạo quản lý cần đảm bảo nguyên tắc là không được trùng giờ nhau. - Các trường cũng không xây dựng một hệ thống quản lý hoàn chỉnh như công khai đến từng sinh viên lịch thi, danh sách cán bộ xem thi… Khi đó vấn đề xếp lịch thi sẽ quay về bài toán xếp lịch thi với ràng buộc về sức chứa của phòng thi và thời gian thi không trùng nhau cùng một hệ thống kết xuất lịch thi đơn giản.. - Bài toán xếp lịch thi thông thường được giải quyết dựa trên hai hướng tiếp cận: thuật giải di truyền (Wong et al., 2002), (Arogundade et al., 2010) hoặc thuật toán tô màu đồ thị (Malkawi et al., 2008). - Trong phần 3, chúng tôi mô hình hóa bài toán xếp lịch thi theo các tiêu chí đề ra ở phần 2.Tiếp theo ở phần 4 chúng tôi phác thảo hệ thống thông tin, ứng dụng kết quả bài toán xếp thời khóa biểu vào ngữ cảnh xếp lịch thi cuối kỳ các lớp. - học phần để xếp lịch thi chung, đồng thời chia sẻ thông tin lịch thi để giảng viên thuận lợi xếp lịch thi riêng. - 2 HIỆN TRẠNG HỆ THỐNG HỖ TRỢ CÔNG TÁC TỔ CHỨC THI KẾT THÚC HỌC PHẦN VÀ QUY TRÌNH ĐỀ XUẤT. - Trên thế giới cũng như tại Việt Nam việc tin học hóa khâu tổ chức thi kết thúc học phần vẫn chưa được quan tâm đúng mức. - Nếu có thì hệ thống cũng khá đơn giản như hệ thống công bố lịch thi của trường đại học Purdue 1. - Hệ thống xếp lịch thi kết thúc học phần hầu như chưa được quan tâm nghiên cứu tại Việt Nam.. - Thực hiện tìm kiếm trên bộ máy tìm kiếm Google chúng tôi chỉ nhận về được một kết quả có liên quan “Thuật toán tô màu đồ thị và ứng dụng xếp lịch thi” (Nghiêm Văn Hưng, 2008), một đề tài nghiên cứu sinh viên của Đại học Đà Nẵng. - Đề tài này ứng dụng thuật toán tô màu đồ thị để giải quyết bài toán xếp lịch thi. - Ứng dụng được xây dựng với một số chức năng cơ bản như cho phép import dữ liệu đăng ký môn học, thực hiện xếp lịch thi và cho xem lịch thi theo mã môn. - Với các chức năng đơn giản như thế thì thực tế chưa đáp ứng được yêu cầu về công tác xếp lịch thi của một trường đại học.. - Trường Đại học Cần Thơ vẫn chưa có hệ thống cho phép quản lý công tác tổ chức thi kết thúc các lớp học phần. - Với cách thức tổ chức thi kết thúc các lớp học phần như hiện nay bao gồm 1 tuần thi riêng (tuần lễ thứ 17) và 1 tuần thi chung (tuần lễ thứ 18) thì áp lực thi cử đối với sinh viên là rất lớn đặc biệt là vào học kỳ 2 của mỗi năm học khi có thời gian 2 tuần nghỉ tết. - Hiện tại, các quy định cần phải tuân thủ khi tổ chức thi kết thúc học phần bao gồm:. - Tuần thi chung được giao cho giáo vụ của khoa phụ trách đào tạo xếp lịch, các giảng viên không được bố trí lịch thi riêng vào tuần thi chung này.. - Hai quy định trên tuy khắc phục được vấn đề trùng lịch thi (về mặt lý thuyết) nhưng lại phát sinh khá nhiều bất cập và đôi khi không thực sự thuận lợi cho sinh viên. - Vấn đề cần giải quyết là cài đặt giải thuật xếp lịch thi tự động cho các lớp học phần đăng ký lịch thi chung với 2 mục tiêu: giảm nhẹ công tác cho cán bộ giáo vụ khoa, có thể tránh được trường hợp sinh viên phải thi cùng 2 môn trong một buổi học.. - Ngoài ra, cần có giải pháp hỗ trợ giảng viên xác định được thời điểm thích hợp cũng như phòng thi phù hợp để xếp lịch thi riêng cho các lớp học phần mà mình phụ trách nhưng chắc chắn rằng sẽ không có sinh viên nào bị trùng lịch thi cũng như trùng phòng thi với các lớp học phần khác.. - Vấn đề trên hoàn toàn có thể giải quyết được nếu như quy trình đăng ký lịch thi riêng, lịch thi chung được xây dựng phù hợp hơn, mềm dẻo hơn và thông tin về thời gian thi, phòng thi của các lớp học phần được chia sẻ một cách phù hợp. - Các giảng viên được yêu cầu tránh bố trí lịch thi riêng vào tuần thi chung tuy nhiên chưa hẳn là sinh viên của lớp học phần do giảng viên đứng lớp có lịch thi vào tuần thi chung.. - Vào các tuần cuối của mỗi học kỳ, khoa sẽ lên kế hoạch chi tiết cho công tác tổ chức thi kết thúc các lớp học phần.. - Giảng viên sẽ đăng ký có hay không lớp học phần mình đang phụ trách sẽ được xếp lịch thi vào tuần thi chung.. - Cán bộ có trách nhiệm thực hiện xếp lịch thi chung (dựa trên kết quả gợi ý của hệ thống xếp lịch thi tự động).. - Công bố lịch thi chung.. - Giảng viên đăng ký lịch thi riêng (có thể đăng ký vào tuần diễn ra lịch thi chung), ưu tiên đúng thời khóa biểu, đăng ký sớm, không trùng lịch của SV với sự hỗ trợ của hệ thống tin học.. - Quy trình đề xuất sẽ giúp giảm tải công tác xếp lịch thi chung cho giáo vụ khoa, giảm áp lực thi cử đối với sinh viên nhờ điều kiện ràng buộc thiết lập đối với giải thuật xếp thời khóa biểu, giảng viên xếp lịch thi riêng thuận lợi hơn nhờ sự hỗ trợ của hệ thống thông tin quản lý lịch thi.. - 3 GIẢI THUẬT XẾP LỊCH THI TỰ ĐỘNG Bài toán xếp thời khóa biểu là bài toán thuộc lớp NP-đầy đủ (NP-Complete), một bài toán không mới với nhiều giải thuật đã được đề xuất như: giải thuật luyện kim, giải thuật di truyền, giải thuật tô màu đồ thị… Tuy nhiên, ưu điểm của giải thuật tô màu đồ thị so với những giải thuật khác là đơn giản trong cài đặt và có thể dễ dàng tích hợp các ràng buộc vào quá trình xây dựng đồ thị. - Mục tiêu (hay nói đúng hơn là các điều kiện) mà chúng tôi đặt ra cho bài toán xếp thời khóa biểu, áp dụng vào ngữ cảnh bài toán xếp lịch thi chung cuối kỳ các lớp học phần đó là:. - Thời gian thi dành cho mỗi lớp học phần được làm tròn theo đơn vị tiết.. - Các lớp học phần của cùng một học phần sẽ được xếp lịch thi cùng một thời điểm.. - Chúng tôi sử dụng cấu trúc đồ thị để mô hình hóa bài toán xếp lịch thi. - V: Đỉnh của đồ thị là các học phần có đăng ký tổ chức thi trong kỳ thi chung.. - E: Cung nối hai đỉnh i và j cho biết có sinh viên thi cả hai học phần i, j trong kỳ thi chung.. - Đầu vào: Danh sách các học phần của các lớp học phần đăng ký lịch thi chung (đỉnh) và bậc của chúng, mối quan hệ sinh viên đăng ký học các lớp học phần (cạnh).. - Đầu ra: Danh sách các học phần đã được tô màu.. - 3.2 Xếp lịch thi. - Đầu vào: Thông tin các lớp học phần của các học phần đã được tô màu (thời gian thi lý thuyết, sỉ số. - Đầu ra: Lịch thi chung cuối kỳ của các lớp học phần.. - Lập danh sách các học phần có màu m, nếu không tìm được học phần nào thì dừng giải thuật.. - Duyệt theo thứ tự mã học phần. - Nếu tất cả các học phần điều đã được xếp lịch thì thực hiện các việc sau:. - Ngược lại, với mỗi học phần được xét:. - Xóa học phần đang xét ra khỏi danh sách. - Chuyển sang học phần kế tiếp.. - Để có thể sắp xếp lịch một cách hiệu quả nhất, khi tất cả các học phần của một màu đều đã được xếp, xét buổi thi cuối cùng có học phần được xếp, ta gọi giải thuật tô màu đồ thị để tô màu cho các học phần đã được xếp trong buổi thi đó cùng với các học phần còn lại, các học phần cùng màu với các học phần đã được xếp sẽ được xếp lịch thi vào buổi đó.. - 4 XÂY DỰNG HỆ THỐNG HỖ TRỢ CÔNG TÁC TỔ CHỨC THI CUỐI KỲ CÁC LỚP HỌC PHẦN. - Dựa trên phân tích ưu nhược điểm của quy trình tổ chức thi kết thúc học phần hiện tại, chúng tôi đề xuất xây dựng một hệ thống tin học với mục tiêu tin học hóa công tác xếp lịch thi chung cũng như công tác đăng ký lịch thi riêng nhằm giải quyết các bất cập nảy sinh trong quá trình tổ chức thi kết thúc các lớp học phần. - Bài toán xếp lịch trước tiên sẽ được giới hạn trong phạm vi một khoa, nghĩa là chỉ thực hiện xếp lịch cho các lớp học phần được quản. - Các giảng viên được phân công giảng dạy các lớp học phần trong mỗi học kỳ. - Lịch thi Thông tin kế hoạch. - lập lịch thi. - lịch thi chung Danh sách lớp học. - Thông tin đăng ký lịch thi riêng. - Lịch thi Lịch thi chung xếp. - Thông tin điều chỉnh lịch thi chung tự động. - Lịch thi chung Lịch thi. - Lịch thi. - Hệ thống quản lý, xếp lịch thi kết thúc học phần Sinh viên. - Lập kế hoạch triển khai tổ chức thi kết thúc học phần: thiết lập kế hoạch chi tiết cho công tác tổ chức thi kết thúc học phần bao gồm thời gian bắt đầu và kết thúc cho phép đăng ký lịch thi chung, thời gian công bố lịch thi chung và đăng ký lịch thi riêng, thời gian công bố lịch thi cho giảng viên, sinh viên.. - Xếp lịch thi chung tự động trong một khoảng thời gian định trước (không để SV bị trùng lịch thi, hạn chế trường hợp SV thi 2 môn trong cùng một buổi).. - Công bố lịch thi chung. - Đăng ký lịch thi riêng. - Ưu tiên cho các lớp học phần tổ chức đúng TKB vào thời gian thi riêng.. - Ưu tiên cho các lớp học phần đăng ký trước và không dẫn đến việc trùng lịch thi của sinh viên.. - Kết xuất lịch thi cho giảng viên, sinh viên Mô hình dữ liệu của hệ thống được trình bày ở Hình 2.. - Hình 2: Mô hình dữ liệu cho hệ thống tổ chức thi cuối kỳ các lớp học phần 5 MỘT SỐ CHỨC NĂNG CHÍNH CỦA. - học phần do khoa mình phụ trách: thời gian đăng ký lịch thi chung, thi riêng. - Hình 3: Giao diện chức năng lập, chỉnh sửa kế hoạch tổ chức kỳ thi Khi đến thời gian đăng ký lịch thi chung, các. - giảng viên có thể đăng ký tổ chức thi chung cho các lớp học phần mà mình phụ trách tại học kỳ đó.. - Hình 4 minh họa cho chức năng đăng ký lịch thi chung của mỗi một giảng viên.. - Sau khi thời gian đăng ký lịch thi chung đã kết thúc, hệ thống sẽ thực hiện xếp lịch thi cho các lớp học phần đăng ký thi chung. - Giáo vụ khoa có thể xem xét điều chỉnh lịch thi chung này. - Giảng viên sẽ thực hiện đăng ký lịch thi riêng khi lịch thi chung đã được công bố. - Hình 5 minh họa cho chức năng đăng ký lịch thi riêng của mỗi một giảng viên.. - Hình 4: Chức năng đăng ký lịch thi chung. - Hình 5: Chức năng đăng ký lịch thi riêng Để thực hiện chức năng đăng ký lịch thi riêng,. - giảng viên cần chọn lớp học phần mà mình muốn đăng ký. - Ban đầu hệ thống sẽ gợi ý lịch thi theo. - Hệ thống căn cứ vào lịch thi chung, căn cứ vào danh sách. - sinh viên của mỗi lớp học phần mà chỉ cho phép giảng viên chọn các phương án thích hợp (phòng còn trống vào thời điểm giảng viên mong muốn tổ chức thi, không có sinh viên trong lớp bị trùng lịch). - vụ khoa sẽ xem được lịch thi theo phòng mà khoa được phân giao quản lý. - Hình 6 minh họa cho chức năng xem lịch thi của những cán bộ được cấp quyền.. - Hình 6: Chức năng xem lịch thi theo tuần, theo phòng 6 KẾT LUẬN. - Trong bài viết này chúng tôi đã cải tiến quy trình tổ chức kỳ thi cuối kỳ cho các lớp học phần thuộc quyền quản lý của một khoa đào tạo bằng cách ứng dụng CNTT để công tác tổ chức kỳ thi được thực hiện một cách đơn giản và hiệu quả hơn.. - Các lớp học phần đăng ký tổ chức thi chung sẽ được hệ thống xếp lịch tự động theo tiêu chí không có sinh viên bị trùng lịch thi và tối thiểu hóa trường hợp sinh viên phải thi 2 môn trong một buổi thi. - Chúng tôi đã thử nghiệm giải thuật xếp lịch thi chung tự động trên dữ liệu lớp học phần vào học kỳ 1 niên khóa 2015-2016 của Khoa Công nghệ Thông tin và Truyền thông. - Tuy nhiên, số lượng các học phần đăng ký thi chung ở một học kỳ tại Khoa Công nghệ Thông tin và Truyền thông là tương đối ít nên chưa thể kiểm chứng được vấn đề về độ giãn cách giữa các lớp học phần thi chung cũng như chưa kiểm tra được điều kiện về số lượng phòng cần bao nhiêu là đủ cho lịch thi chung. - của giải thuật xếp lịch thi tự động thay vì kiểm tra một cách thủ công như hiện nay.