Báo cáo Xây dựng hệ thống hỗ trợ xếp lịch thi cho trường đại học Sư phạm Kỹ thuật Tp.HCM (Phần 1)

Nội dung text: Báo cáo Xây dựng hệ thống hỗ trợ xếp lịch thi cho trường đại học Sư phạm Kỹ thuật Tp.HCM (Phần 1)

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH CÔNG TRÌNH NGHIÊN CỨU KHOA HỌC CẤP TRƯỜNG XÂY DỰNG HỆ THỐNG HỖ TRỢ XẾP LỊCH THI CHO TRƯỜNG ÐHS K C SPKT0 0 3 9 5 9 TP.HCM MÃ SỐ: T2013 - 37 S KC 0 0 5 4 3 6 Tp. Hồ Chí Minh, 2013
2. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH BÁO CÁO TỔNG KẾT ĐỀ TÀI KH&CN CẤP TRƢỜNG XÂY DỰNG HỆ THỐNG HỖ TRỢ XẾP LỊCH THI CHO TRƢỜNG ĐH SPKT TP.HCM Mã số: T2013 - 37 Chủ nhiệm đề tài: KS. Phùng Quang Ngọc TP. HCM, 12/2013 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH KHOA CÔNG NGHỆ THÔNG TIN 1
3. BÁO CÁO TỔNG KẾT ĐỀ TÀI KH&CN CẤP TRƢỜNG XÂY DỰNG HỆ THỐNG HỖ TRỢ XẾP LỊCH THI CHO TRƢỜNG ĐH SPKT TP.HCM Mã số: T2013 - 37 Chủ nhiệm đề tài: KS. Phùng Quang Ngọc Thành viên đề tài: ThS. Trần Công Tú TP. HCM, 12/2013 MỤC LỤC DANH MỤC CÁC HÌNH III DANH MỤC CÁC BẢNG IV THÔNG TIN KẾT QUẢ NGHIÊN CỨU V 2
4. CHƢƠNG 1: MỞ ĐẦU 6 1.1 TổNG QUAN 6 1.2 TÍNH CấP THIếT CủA Đề TÀI 2 1.3 MụC TIÊU Đề TÀI 3 1.4 CÁCH TIếP CậN 3 1.5 PHƢƠNG PHÁP NGHIÊN CứU 3 1.6 ĐốI TƢợNG TƢợNG VÀ PHạM VI NGHIÊN CứU 4 1.6.1 Các đối tượng nghiên cứu: 4 1.6.2 Phạm vi nghiên cứu: 4 CHƢƠNG 2 GIẢI THUẬT XẾP LỊCH THI 4 2.1 HƢớNG TIếP CậN GIảI QUYếT BÀI TOÁN XếP LịCH 4 2.2 GIảI THUậT XếP LịCH THI Sử DụNG THUậT TOÁN TÔ MÀU 5 2.3 HIệN THựC HOÁ THUậT TOÁN 6 2.3.1 Bước 1 Tạo ma trận kề 6 2.3.2 Bước 2 Tô màu đồ thị 7 2.3.3 Bước 3: Gán thời gian cho các nhóm thi và xếp phòng 8 CHƢƠNG 3 : XÂY DỰNG CHƢƠNG TRÌNH 10 3.1 KHảO SÁT HIệN TRạNG 10 3.2 PHÂN TÍCH THIếT Kế 12 3.2.1 Thiết kế usecase 12 3.2.2 Mô tả usecase 13 3.2.1 Mô hình hóa yêu cầu: 16 3.2.2 Thiết kế cơ sở dữ liêụ 20 3.2.3 Thiết kế xử lý: 25 3.3 GIAO DIệN PHầN MềM 36 3.3.1 Chọn môn không thi: 36 3.3.2 Ghép nhóm thi: 36 3.3.3 Lập danh sách sinh viên bị cấm thi: 37 3.3.4 Thiết lập thông số đầu vào cho kì thi: 37 3.3.5 Chọn phòng không tổ chức thi: 38 3.3.6 Xếp lịch thi tự động: 39 3.3.1 Xếp lịch thi thủ công: 39 3.3.1 Chỉnh sửa kết quả xếp lịch thi: 40 3.3.2 Xem lịch thi sinh viên dạng danh sách: 40 3.3.3 Xem lịch thi sinh viên dạng lịch: 41 3.3.4 Xem danh sách môn thi theo đợt: 41 3.3.5 Xem danh sách sinh viên thi theo phòng: 42 3.3.6 Xem danh sách sinh viên thi theo môn: 42 3.3.7 Xem danh sách môn học: 43 3.3.8 Xem danh sách sinh viên: 43 ii
5. 3.3.9 Xem danh sách phòng: 44 CHƢƠNG 4 KẾT LUẬN 44 KếT QUả ĐạT ĐƢợC 44 HạN CHế 45 HƢớNG PHÁT TRIểN 45 TÀI LIỆU THAM KHẢO 45 DANH MỤC CÁC HÌNH Hình 3.1: Lược đồ chức năng 12 Hình 3.2: Xem dữ liệu giảng viên 16 Hình 3.3: Xem dữ liệu phòng 16 Hình 3.4:Xem dữ liệu sinh viên 17 Hình 3.5: Xem dữ liệu môn học 18 Hình 3.6: Tra cứu lịch thi sinh viên 19 Hình 3.7: Cơ sở dữ liệu 20 Hình 3.8: Xử lý chính xem danh sách sinh viên 26 Hình 3.9: Xử lý chính chọn thiết lập 27 Hình 3.10: Xử lý chính chọn môn thi 28 Hình 3.11: Xử lý chính chọn sinh viên 29 Hình 3.12: Xử lý chính xem lịch thi của một sinh viên 29 Hình 3.13:Xử lý chính xem giáo viên 30 Hình 3.14: Xử lý chính xem phòng thi 31 Hình 3.15:Xử lý chính xem môn học 32 Hình 3.16: Xử lý chính chọn phòng thi 33 Hình 3.17: Xử lý chính xem lịch thi của một phòng 34 Hình 3.18: Xử lý chính xem lịch thi của sinh viên theo phòng 34 Hình 3.19: Xử lý chính hình xem lịch thi của sinh viên theo môn 35 Hình 3.20: Giao diện quản lý các môn không tổ chức thi 36 Hình 3.21: Giao diện ghép các nhóm thi 36 Hình 3.22: Giao diện lập danh sách sinh viên bị cấm thi 37 Hình 3.23: Giao diện thiết lập đầu vào 37 Hình 3.24: Giao diện chọn phòng không tổ chức thi 38 Hình 3.25: Giao diện xếp lịch thi tự động 39 Hình 3.26: Giao diện xếp lịch thi thủ công 39 Hình 3.27: Giao diện chỉnh sửa kết quả xếp lịch thi 40 Hình 3.28: Giao diện xem lịch thi sinh viên dạng danh sách 40 Hình 3.29: Giao diện xem lịch thi của sinh viên dạng lịch 41 Hình 3.30: Giao diện quản lý các môn thi theo đợt 41 iii
6. Hình 3.31: Giao diện xem danh sách sinh viên thi theo phòng 42 Hình 3.32: Giao diện danh sách sinh viên thi theo môn 42 Hình 3.33: Giao diện xem danh sách môn học 43 Hình 3.34: Giao diện xem danh sách sinh viên 43 Hình 3.35: Giao diện xem danh sách phòng 44 DANH MỤC CÁC BẢNG Bảng 3.1: Mô tả usecase nhân viên phòng đào tạo 13 Bảng 3.2 - Mô tả usecase Giảng Viên 14 Bảng 3.3 - Mô tả Usecase Sinh Viên 14 Bảng 3.4 - Các quy định liên quan 15 Bảng 3.5 - Bảng sinh viên 21 Bảng 3.6 - Bảng ca thi 21 Bảng 3.7 - Bảng phân công dạy 21 Bảng 3.8 - Bảng bộ môn 22 Bảng 3.9 - Bảng chuyên ngành 22 Bảng 3.10 - Bảng giáo viên 22 Bảng 3.11 - Bảng khoa 22 Bảng 3.12 - Bảng khối 23 Bảng 3.13 - Bảng lịch học vụ 23 Bảng 3.14 - Bảng lớp 23 Bảng 3.15 - Bảng môn học 24 Bảng 3.16 - Bảng nhóm 24 Bảng 3.17 - Bảng đăng kí môn học 24 Bảng 3.18 - Bảng phòng 25 Bảng 3.19 - Bảng thi 25 Bảng 3.20 - Danh sách các xử lý màn hình xem sinh viên 25 Bảng 3.21 - Danh sách các xử lý màn hình chọn thiết lập 26 Bảng 3.22 - Danh sách các xử lý màn hình chọn môn thi 27 Bảng 3.23 - Danh sách các xử lý màn hình chọn sinh viên 28 Bảng 3.24 - Danh sách các xử lý màn hình xem lịch thi của sinh viên 29 Bảng 3.25 - Danh sách các xử lý màn hình chọn giáo viên 30 Bảng 3.26 - Danh sách các xử lý màn hình xem phòng thi 31 Bảng 3.27 - Danh sách các xử lý màn hình xem môn học 32 Bảng 3.28 - Danh sách các xử lý màn hình chọn phòng thi 33 Bảng 3.29 - Danh sách xử lý màn hình xem lịch thi của một phòng 33 Bảng 3.30 - Danh sách xử lý màn hình xem lịch thi của SV theo phòng 34 Bảng 3.31 - Danh sách xử lý màn hình xem lịch thi SV theo môn 35 TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM THÀNH PHỐ HỒ CHÍ MINH Độc lập - Tự do - Hạnh phúc KHOA CÔNG NGHỆ THÔNG TIN iv
7. Tp. HCM, Ngày tháng năm THÔNG TIN KẾT QUẢ NGHIÊN CỨU 1. Thông tin chung: - Tên đề tài: Xây dựng hệ thống hỗ trợ xếp lịch thi cho trƣờng đại học Sƣ phạm Kỹ thuật Tp.HCM - Mã số: T2013-27 - Chủ nhiệm: KS. Phùng Quang Ngọc - Cơ quan chủ trì: Trƣờng ĐH Sƣ phạm Kỹ thuật TP.HCM - Thời gian thực hiện:1/2013 đến 12/2013 2. Mục tiêu: Xây dựng thành công hệ thống hỗ trợ xếp lịch thi cho trƣờng ĐH Sƣ phạm Kỹ thuật TP.HCM 3. Tính mới và sáng tạo: Đề tài mang tính ứng dụng nên không đòi hỏi tính mới và sáng tạo. 4. Kết quả nghiên cứu: Một báo cáo khoa học hoàn chỉnh, làm tài liệu cho giảng viên và sinh viên tham khảo để phát triển linh hoạt hệ thống, tích hợp thêm các module, chức năng khác. 5. Sản phẩm: Một ứng dụng hỗ trợ xếp lịch thi cho phòng Đào tạo trƣờng ĐH SPKT TP.HCM. 6. Hiệu quả, phƣơng thức chuyển giao kết quả nghiên cứu và khả năng áp dụng: Có thể triển khai thử nghiệm, nâng cấp thêm và chuyển giao. Trƣởng Đơn vị Chủ nhiệm đề tài (ký, họ và tên) (ký, họ và tên) INFORMATION ON RESEARCH RESULTS v
8. 1. General information: Project title:Develop a software aided arrange the exam schedule at Universiti of Technical Education Ho Chi Minh city Code number: T2013-37 Coordinator: BE. Phung Quang Ngoc Implementing institution: Ho Chi Minh City University of Technical Education Duration: from Jan 2013 to Dec 2013 2. Objective(s): Building efficiently the system for making exam schedule at Ho Chi Minh City University of Technical Education 3. Creativeness and innovativeness: Project has great applicability, so it does not require creativeness and innovativeness. 4. Research results: -A full work-out scientific report. -Lecturer and student can use this as a reference. Then they can flexibly develop the system and add other modules and functions. 5. Products: An application for making exam schedule at Academy Affair ofuniversity of Technical Education Ho Chi Minh City 6. Effects, transfer alternatives of research results and applicability: The application can be launched, updated, and transferred. CHƢƠNG 1: MỞ ĐẦU 1.1 Tổng quan Bài toán lập lịch là bài toán đã ra đời từ rất lâu cùng với lịch sử phát triển của loài ngƣời. Tuy nhiên cho đến ngày nay nó vẫn là bài toán khó và chƣa có lời giải nào là tối ƣu cho tất cả các trƣờng hợp mà chỉ tốt trong một số điều kiện cụ thể. vi
9. Trong các trƣờng học từ cấp tiểu học, phổ thông cho tới đại học thì việc lập lịch là công việc mất rất nhiều thời gian và phải thực hiện thƣờng xuyên trong mỗi học kỳ, mỗi năm học. Từ lập thời khóa biểu giảng dạy cho đến xếp lịch thi học kỳ đều đƣợc các trƣờng thực hiện thủ công hay bán tự động. Trong nƣớc có một số phần mềm quản lý trƣờng học có hỗ trợ chức năng xếp lịch thi nhƣ: F-School, Vschool, EduMa . Tuy nhiên, đối với các phần mềm này đều là các phần mềm có phí, và chức năng xếp lịch thi trong các phần mềm này không thể sử dụng nhƣ là một phần mềm riêng biệt. Do đó không thể tích hợp với các hệ thống có sẵn khác. 1.2 Tính cấp thiết của đề tài Tin học hóa là một trong các yêu cầu cấp thiết của các trƣờng đại học nói chung và trƣờng đại học Sƣ phạm Kỹ thuật Thành phố Hồ Chí Minh nói riêng. Hệ thống hiện tại chƣa kết nối đƣợc với hệ thống đăng ký môn học của sinh viên, quá trình đồng bộ dữ liệu giữa các hệ thống phải thực hiện thủ công. Do đó cần có một công cụ hỗ trợ xếp lịch hiệu quả, kết nối đƣợc với hệ thống đăng ký môn học hiện có. Với hình thức học chế tín chỉ, sinh viên có thể chủ động chọn đăng kí môn học theo kế hoạch của mình, do đó mỗi sinh viên sẽ có một lịch học và lịch thi riêng. Điều này làm cho việc xếp lịch thi trở nên khó khăn hơn. Việc xếp lịch thủ công cho hàng ngàn sinh viên là không khả thi mà cần phải có sự trợ giúp của các phần mềm máy tính. Hiện tại, phòng đào tạo của trƣờng Đại học Sƣ phạm Kỹ thuật TP.HCM đang sử dụng phần mềm quản lý đào tạo EduSoft trong đó đã có phần xếp lịch thi, tuy nhiên còn một số hạn chế nhƣ: - Chỉ chạy trên windows và dùng trong nội bộ mạng LAN chứ không hỗ trợ giao diện web. - Cơ sở dữ liệu sử dụng Foxpro và độc lập với hệ thống Đăng ký môn học hiện có: 2
10. + Sau khi đăng ký môn học xong, dữ liệu đăng ký môn học của sinh viên phải đƣợc export sang định dạng file Foxpro để có thể import và phần mềm Edusoft để xếp lịch thi. + Sau khi xếp lịch thi xong phải chuyển dữ liệu xếp lịch đƣợc về lại SQL để đƣa lên hệ thống Đăng ký môn học để hiển thị cho sinh viên. Việc liên tục chuyển đổi qua lại nhƣ vậy tiềm ẩn nguy cơ phát sinh lỗi rất cao. - Phần xuất kết quả xếp lịch không hỗ trợ sinh viên, giáo viên xem lịch thi của mình. Với những lý do trên, đề tài nhắm tới một phần mềm xếp lịch thi đáp ứng các yêu cầu sau: - Chạy trên nền web cho phép xếp lịch thi bằng một máy tính bất kỳ. - Sử dụng chung cơ sở dữ liệu SQL với phần mềm Đăng ký môn học hiện có. - Hỗ trợ nhiều ngƣời sử dụng. - Kết quả cho phép sinh viên và giáo viên có thể xem trực tiếp thông tin lịch thi trên giao diện web. 1.3 Mục tiêu đề tài Xây dựng thành công hệ thống hỗ trợ xếp lịch thi cho trƣờng ĐH Sƣ phạm Kỹ thuật TP.HCM, qua đó góp phần từng bƣớc tin học hóa quản lý trong nhà trƣờng. 1.4 Cách tiếp cận - Nghiên cứu, ứng dụng những công cụ hiện đại của CNTT và truyền thông vào trong giáo dục và đào tạo. Cụ thể là xây dựng hệ thống quản lý và xếp lịch thi bán tự động cho trƣờng đại học SPKT 1.5 Phƣơng pháp nghiên cứu - Khảo sát, phân tích hiện trạng thực tế từ đó đề ra giải pháp và quy trình nghiệp vụ tổng quát. - Nghiên cứu các thuật toán lập lịch áp dụng vào bài toán xếp lịch thi của trƣờng đại học. 3
11. 1.6 Đối tƣợng tƣợng và phạm vi nghiên cứu 1.6.1 Các đối tƣợng nghiên cứu: - Quy trình xếp lịch thi tại trƣờng đại học SPKT TP.HCM - Thuật toán xếp lịch. 1.6.2 Phạm vi nghiên cứu: Phạm vi nghiên cứu của đề tài chỉ giới hạn trong các quy trình nghiệp vụ tại trƣờng Đại học Sƣ phạm Kỹ thuật TP.HCM. CHƢƠNG 2 GIẢI THUẬT XẾP LỊCH THI 2.1 Hƣớng tiếp cận giải quyết bài toán xếp lịch Có rất nhiều giải thuật có thể áp dụng để giải quyết bài toánlịch trong đó có thể kể đến: Tô màu đồ thị (Graph Coloring) Mô phỏng tôi thép (Anealing Simulate) Di Truyền (Generics) Tìm kiếm Tabu (Tabu Search) Tìm kiếm tham lam, hoặc theo kinh nghiệm (heuristic) Giải thuật Anealing Simulate & Generics có nguyên tắc khá giống nhau đó là sinh ngẫu nhiên một lời giải, sau đó biến đổi trên lời giải ban đầu một cách ngẫu nhiên để tạo ra các lời giải mới. Về lý thuyết thì các giải thuật này chạy càng lâu càng cho ra lời giải tốt hơn, tuy nhiên vì dựa nhiều vào tính ngẫu nhiên nên rất khó để kiểm soát tốc độ hội tụ cũng nhƣ độ tốt của lời giải. Phƣơng án tìm kiếm Tabu đƣợc thực hiện dựa trên tƣ tƣởng tìm kiếm cục bộ. Xuất phát từ một lời giải ban đầu (có thể tạo ra bằng cách sinh ngẫu nhiên), tìm kiếm các lời giải lân cận (có thể biến đổi đƣợc từ lời giải đầu) và chọn lời giải tốt nhất trong số các lân cận. Lặp lại quá trình đó với lời giải mới vừa đƣợc chọn tới khi nào không có lân cận nào tốt hơn lời giải hiện tại hoặc tới khi đạt đƣợc điều kiện dừng. 4
12. Phƣơng pháp tìm kiếm tham lam thƣờng lập lịch bằng cách sắp xếp mức độ ƣu tiên của các ràng buộc mềm sau đó tiến hành xếp lịch sao cho đáp ứng các ràng buộc mềm theo thứ tự đã sắp xếp. Ràng buộc càng khó đạt đƣợc sẽ đƣợc ƣu tiên đáp ứng trƣớc. Giải thuật tô màu đồ thị là giải thuật dùng để tô màu cho các đỉnh của một đồ thị sao cho 2 cặp đỉnh kề nhau bất kỳ phải có màu khác nhau.Đối với bài toán xếp lịch, đỉnh của đồ thị thể hiện một phần tử cần xếp lịch, các đỉnh của đồ thị kề nhau hay không thể hiện giữa các đỉnh có vi phạm các ràng buộc hay không. Bài toán xếp lịch cho các phần tử sao cho thỏa mãn các ràng buộc đƣợc giải quyết bằng cách tô màu cho các đỉnh của đồ thị sao cho không có cặp đỉnh kề nhau nào có cùng màu. Có thể sử dụng các heuristic trong quá trình tô màu. 2.2 Giải thuật xếp lịch thi sử dụng thuật toán tô màu Dữ liệu đầu vào của bài toán xếp lịch thi gồm có: Danh sách các nhóm thi: Danh sách các lớp học phần cần xếp lịch thi. Lịch học của từng sinh viên: Danh sách các môn học của sinh viên cần phải xếp lịch thi. Thông tin phòng thi: Danh sách các phòng học đƣợc dùng để thi, khả năng chứa của phòng và lịch của phòng. Các ràng buộc của quá trình xếp lịch thi: o Mỗi sinh viên chỉ thi tối đa một môn tại một thời điểm. o Lịch thi phải đƣợc xếp trong khoảng thời gian từ Ngày bắt đầu tới Ngày kết thúc thi. o 2 môn thi liên tiếp của một sinh viên phải cách nhau tối thiểu D ca thi. o Các sinh viên học cùng lớp học phần phải thi cùng lúc. Đầu ra của bài toán: Danh sách lịch thi (gồm có ngày thi ca thi phòng thi)của từng sinh viên, từng môn học. 5
13. Mô hình lại bài toán xếp lịch thi dƣới dạng đồ thị nhƣ sau: Có thể giải bài toán lập lịch thi bằng mô hình đồ thị, với các đỉnh là các môn thi (lớp học phần), có một cạnh nối hai đỉnh nếu có sinh viên phải thi cả hai môn đƣợc biểu diễn bằng hai đỉnh này. Thời gian thi của mỗi môn đƣợc biểu thị bằng các màu khác nhau. Nhƣ vậy việc lập lịch thi sẽ tƣơng ứng với việc tô màu đồ thị này. Việc mô hình mỗi đỉnh là một môn thi đã giải quyết đƣợc ràng buộc các sinh viên học cùng lớp học phần phải thi cùng lúc. Sau khi tô màu xong, ta có danh sách các màu đƣợc sử dụng để tô cho các đỉnh của đồ thị. Các môn thi đƣợc tô màu khác nhau nghĩa là phải đƣợc xếp lịch vào các khoảng thời gian khác nhau. Điều đó giúp đáp ứng ràng buộc về trùng lịch thi của sinh viên: sinh viên không thi 2 môn cùng lúc. Ta sẽ sử dụng các heuristic để giải quyết các ràng buộc còn lại khi tiến hành phẩn bổ thời gian, phòng thi cho các màu. 2.3 Hiện thực hoá thuật toán 2.3.1 Bƣớc 1 Tạo ma trận kề 2.3.1.1 Mục đích Tạo đồ thị input nhằm thể hiện các ràng buộc của bài toán và làm dữ liệu để tô màu đồ thị. 2.3.1.2 Dữ liệu Danh sách tên các đỉnh MãMônHọc_Lớp1_Lớp2_ sẽ đƣợc lấy từ List Groups Ma trận kề thể hiện đồ thị sẽ đƣợc lƣu vào int[,] AdjacencyMatrix 2.3.1.3 Thuật toán Duyệt qua từng nhóm trong Groups, kiểm tra xem thử có tồn tại cạnh nối đỉnh đó với từng đỉnh khác không, rồi điền vào AdjacencyMatrix. AdjacencyMatrix[i,j] = 0 : Nếu không có sinh viên học cùng lúc Groups[i] và Groups[j]. 6
14. AdjacencyMatrix[i,j] = 1 : Nếu có sinh viên học cùng lúc Groups[i] và Groups[j]. 2.3.2 Bƣớc 2 Tô màu đồ thị 2.3.2.1 Mục đích Chia các nhóm thi thành các ca thi, mỗi ca sẽ chứa các nhóm thi có thời gian thi đƣợc phép trùng nhau! Mỗi ca sẽ đƣợc tô một màu khác nhau. 2.3.2.2 Dữ liệu Đầu vào: Đồ thị đƣợc đọc vào từ ma trận kề đƣợc tạo ở bƣớc 1 Danh sách sinh viên bị cấm thi Dictionary >IgnoreStudents Đầu ra: Kết quả tô màu sẽ đƣợc lƣu vào int[] Colors, số lƣợng màu sẽ đƣợc lƣu vào int ColorNumber 2.3.2.3 Thuật toán void Coloring() { int x,y; int ColorNumber = 0; int VerticesInCommon = 0; while (unprocessed>0) // Trong khi vẫn còn có đỉnh chưa được tô màu { x = MaxDegreeVertex(); // Tìm 1 đỉnh có bậc cao nhất ColorNumber ++; color[x] = ColorNumber; // Cho nó 1 cái màu mới unprocessed ; // Tìm tập hợp các đỉnh không phải hàng xóm của x 7
15. UpdateNN(ColorNumber); while (NNCount>0) // trong khi các đỉnh ko phải hàng xóm > 0 { // Tìm y, là 1 đỉnh có nhiều hàng xóm chung với x nhất // VerticesInCommon là số hàng xóm lớn nhất y = FindSuitableY(ColorNumber, VerticesInCommon); // Trong trường hợp VerticesInCommon = 0 // y được xác đinh là đỉnh có bậc cao nhất trong NN //(tập ko hàng xóm của x) if (VerticesInCommon == 0) y = MaxDegreeInNN(); // màu y cùng màu với x color[y] = ColorNumber; unprocessed ; // 1 đỉnh vừa được tô, giảm đi UpdateNN(ColorNumber); // cập nhật NN } } } 2.3.3 Bƣớc 3: Gán thời gian cho các nhóm thi và xếp phòng 2.3.3.1 Mục đích Đảm bảo ràng buộc 2 môn thi liên tiếp của 1 sinh viên bất kỳ cách nhau ít nhất n ca thi. Gán thời gian mặc định cho các nhóm thi. Phân phòng cho từng nhóm thi. Nếu đã hết phòng cho nhóm đó thì chuyển nhóm đó sang ca thi tiếp theo và sửa lại thời gian thi cho các môn thi sau. 2.3.3.2 Dữ liệu Đầu vào: Thời gian thi của các ca List Shifts 8
16. Danh sách phòng thi cho từng ca List Rooms Các thiết lập của ngƣời dùng: Options Options Đầu ra: Thời gian thi của mỗi nhóm thi: DateTime[] GroupsTime Phòng thi cho từng nhóm: List [] GroupsRoom Danh sách sinh viên theo phòng tƣơng ứng với từng nhóm thi cụ thể List [][] GroupsRoomStudents 2.3.3.3 Thuật toán Bƣớc 1: Gán thời gian mặc định cho từng nhóm thi theo từng cụm thi (các nhóm cùng đƣợc tô một màu) sao cho đảm bảo rằng các môn khác màu nhau có thời gian thi cách nhau ít nhất là n ca thi Bƣớc 2: Lấy danh sách sinh viên tham gia thi theo từng nhóm thi cụ thể để chia phòng, danh sách sinh viên đƣợc sắp xếp theo tên sinh viên Bƣớc 3: Chia phòng cho từng môn cùng ca. Cụ thể nhƣ sau: B1: Lấy danh sách các nhóm thi trong ca chƣa xếp phòng B2: Nếu danh sách vừa lấy có phần tử thì qua bƣớc 3 còn không thì kết thúc hàm. B3: Duyệt qua từng nhóm trong danh sách vừa lấy, xếp phòng cho nhóm đó (Thủ tục RoomArrangementForOneGroup). Sau khi xếp phòng cho tất cả các phần tử trong danh sách, quay lại bƣớc 1. Thủ tục RoomArrangementForOneGroup để xếp phòng cho 1 nhóm B1: Nếu số lƣợng sinh viên thi trong nhóm vƣợt quá tổng sức chứa của tất cả các phòng đƣợc sử dụng ở tất cả các ca thì dừng thuật toán và thông báo lỗi thiếu phòng. B2: Trong khi số lƣợng sinh viên chƣa xếp phòng cho nhóm hiện tại lớn hơn 0 thì qua bƣớc 3, còn không thì tiến hành lập danh sách sinh viên cho nhóm đó. (Hàm MakeStudentList.) 9
17. B3: Nếu còn phòng thì phân phòng đó cho nhóm hiện tại, giảm số lƣợng sinh viên chƣa xếp phòng đi 1 lƣợng bằng sức chứa của phòng đó sau đó quay lại bƣớc 2, ngƣợc lại thì qua bƣớc 4. B4: Hết phòng, nên giãn ca thi! Xóa danh sách các phòng đã phân cho nhóm hiện tại, chuyển môn hiện tại qua ca tiếp theo, đồng thời nếu thời gian ở ca tiếp theo lớn hơn thời gian lớn nhất của các nhóm thi cùng màu với nhóm thi hiện tại thì chuyển các nhóm thi ở các ca sau ra sau một ca để tránh bị trùng giờ và đảm bảo tính ràng buộc. Thủ tụcMakeStudentList nhằm phân chia danh sách sinh viên trong nhóm theo các phòng đƣợc phân đảm bảo điều kiện, số lƣợng sinh viên thi trong các phòng không quá chênh lệch nhau về số lƣợng! CHƢƠNG 3 : XÂY DỰNG CHƢƠNG TRÌNH 3.1 Khảo sát hiện trạng Quy trình xếp lịch thi tại trƣờng ĐH SPKT TP.HCM hiện tại nhƣ sau. Để thực hiện việc xếp lịch thi cuối mỗi học kỳ, nhân viên phòng đào tạo đảm nhận nhiệm vụ xếp lịch sẽ phải thực hiện các thao tác sau: Lên danh sách các môn sẽ thi từ danh sách do các khoa gởi về (khoảng 700 môn). Lên danh sách các sinh viên bị cấm thi do giáo viên các môn đƣa lên. Lên danh sách các phòng học sẽ đƣợc sử dụng để thi. Thiết lập thời gian sẽ tổ chức thi (theo lịch học vụ). Sau các thao tác chuẩn bị, nhân viên xếp lịch thi sử dụng chức năng xếp lịch thi trong phần mềm EduSoft để tự động xếp lịch thi sơ bộ (thƣờng nhân viên phải để cho máy chạy suốt đêm mới xong). > Xếp lịch lại thủ công cho phù hợp > Xếp các môn thi vào phòng > Phân công giáo viên coi thi (phần này thƣờng do thƣ ký khoa làm) 10
18. > Cập nhật cơ sở dữ liệu để sinh viên có thể xem lịch thi của mình qua trang web trƣờng > In lịch coi thi gởi về khoa, khoa đƣa cho giáo viên > In danh sách sinh viên thi theo phòng > In danh sách phòng và ngày giờ sửa dụng đƣa cho quản lý phòng > In danh sách các môn thi (theo khoa) và đƣa về khoa. Giảng viên sẽ nhận lịch coi thi từ khoa. Sinh viên sẽ xem lịch thi của mình từ trang web của trƣờng. Trƣởng phòng đào tạo có nhiệm vụ quản lý trực tiếp quá trình sắp lịch thi, mọi vấn đề đều phải báo qua trƣởng phòng đào tạo và trƣởng phòng đào tạo có quyền quyết định mọi thông tin về kì thi. 11
19. 3.2 Phân tích thiết kế 3.2.1 Thiết kếusecase Hình 3.1: Lược đồ chức năng 12
20. 3.2.2 Mô tả usecase 3.2.2.1 Mô tả usecase nhân viên phòng đào tạo: Quy định công thức STT Chức năng Loại liên quan 1 Đăng nhập QĐ_DangNhap 2 Lập danh sách môn ƣu tiên Lƣu Trữ QĐ_MonUuTien 3 Lập danh sách môn tổ chức thi Lƣu Trữ QĐ_MonToChucThi 4 Ghép nhóm thi Lƣu Trữ QĐ_GhepNhomThi 5 Lập danh sách cấm thi Lƣu Trữ QĐ_DSCamThi 6 Thiết lập thông số Lƣu Trữ QĐ_ThongSo 7 Chọn ca không thi Lƣu Trữ QĐ_CaKhongThi 8 Chọn phòng không thi Lƣu Trữ QĐ_PhongKhongThi 9 Xếp lịch thi thủ công Lƣu Trữ QĐ_XepThuCong 10 Xếp lịch thi tự động Lƣu Trữ QĐ_XepTuDong 11 Sửa kết quả Lƣu Trữ QĐ_SuaKetQua 12 Xem dạng lịch theo sinh viên Tra Cứu QĐ_XemLichSV 13 Xem dạng lịch theo phòng Tra Cứu QĐ_XemLichPhong 14 Danh sách lịch thi mỗi sinh viên. Tra Cứu QĐ_XemDSMoiSV 15 Danh sách phòng thi Tra Cứu QĐ_XemDSPhong 16 Danh sách sinh viên theo phòng. Tra Cứu QĐ_XemSV_Phong. 17 Danh sách sinh viên theo môn. Tra Cứu QĐ_XemSV_Mon 18 Lịch mở phòng Tra Cứu 19 Danh sách thi theo đợt. Tra Cứu QĐ_ThiTheoDot 20 Xem CSDL môn học Tra cứu 21 Xem CSDL sinh viên Tra cứu 22 Xem CSDL phòng học Tra cứu Bảng 3.1: Mô tả usecase nhân viên phòng đào tạo 13
21. 3.2.2.2 Mô tả usecase Giảng Viên: Quy định công thức STT Chức năng Loại liên quan 1 Đăng nhập QĐ_DangNhap 2 Danh sách lịch thi mỗi sinh viên Tra Cứu QĐ_XemDSMoiSV 3 Danh sách phòng thi Tra Cứu 4 Danh sách sinh viên theo phòng Tra Cứu QĐ_XemSV_Phong. 5 Danh sách sinh viên theo môn Tra Cứu QĐ_XemSV_Mon 6 Lịch mở phòng Tra Cứu QĐ_MoPhong 7 Danh sách thi theo đợt Tra Cứu QĐ_ThiTheoDot Bảng 3.2 - Mô tả usecase Giả ng Viên 3.2.2.3 Mô tả Usecase Sinh Viên Quy định công thức STT Chức năng Loại liên quan 1 Đăng nhập QĐ_DangNhap 2 Danh sách lịch thi mỗi sinh viên Tra Cứu QĐ_XemDSMoiSV Bảng 3.3 - Mô tả Usecase Sinh Viên 14
22. S K L 0 0 2 1 5 4