Thạc Sĩ Xây dựng công cụ hỗ trợ tự động hoá lập lịch thi tại trường đại học

LUẬN VĂN THẠC SĨ
NĂM 2011


UĐề mụcU UTrang
0BLỜI CAM ĐOAN i
1BLỜI CẢM ƠN .ii
2BTÓM TẮT iii
3BMỤC LỤC iv
4BDANH MỤC HÌNH .vii
5BDANH MỤC BẢNG x
Chương 1. GIỚI THIỆU ĐỀ TÀI
1.1 6BDẫn nhập .1
1.2 7BBài toán lập lịch thi tại Trường Đại học Lạc Hồng (LHU) .2
1.2.1 Thực trạng .2
1.2.2 Nhu cầu 3
1.3 8BKhảo sát các công trình liên quan đến lập lịch thi 4
1.4 9BMục tiêu thực hiện đề tài – Đề xuất giải pháp mới cho bài toán lập lịch thi tại một trường đại học .5
1.5 10BTóm tắt nội dung nghiên cứu .7
1.5.1 Ý tưởng thực hiện 7
1.5.2 Xác định các kỹ thuật chính sẽ sử dụng .9
1.6 11BQui trình và phương pháp thực hiện 11
1.7 12BPhạm vị thực hiện đề tài .11
1.8 13BHướng phát triển .14
1.9 14BSơ lược cấu trúc luận văn .15

Chương 2. CƠ SỞ LÝ THUYẾT
2.1 Thuật giải di truyền hướng đến tối ưu lịch thi 16
2.1.1 Một thuật giải di truyền đơn giản 17
2.1.2 Các toán tử của thuật giải di truyền 20
2.1.3 Lưu đồ xử lý giải thuật 28
2.2 Tính toán mờ trong việc hình thành lịch thi và hỗ trợ giải thuật di truyền tối ưu lịch thi .29
2.2.1 Khái niệm tập mờ 30
2.2.2 Các phép toán trên tập mờ .32
2.2.3 Suy diễn mờ .34

Chương 3. XÂY DỰNG CHƯƠNG TRÌNH
3.1 Phân tích và thiết kế cơ sở dữ liệu .37
3.1.1 Xác định thực thể .37
3.1.2 Mô hình thực thể kết hợp 37
3.1.3 Mô hình quan hệ 37
3.1.4 Mô hình dữ liệu .39
3.1.5 Ý nghĩa .41
3.2 Các bước xử lý 45
3.3 Xây dựng quần thể 47
3.3.1 Xây dựng vế trái 47
3.3.2 Xây dựng vế phải .47
3.3.3 Ráp vế phải vào vế trái .48
3.3.4 Tính toán mờ số thí sinh và sức chứa 52
3.4 Lượng giá quần thể .57
3.4.1 Xây dựng chuẩn đánh giá quần thể .57
3.4.2 Kết quả đánh giá các cá thể trong quần thể 60
3.5 Chọn cá thể tốt 61
3.6 Thực hiện lai .62
3.7 Thực hiện đột biến 63
3.8 Tinh chỉnh lịch thi .64
3.9 Tìm kiếm và điều động CBCT 64

Chương 4. KẾT QUẢ ĐẠT ĐƯỢC
4.1 Xây dựng được phiên bản đầu phần mềm demo LLTdh .65
4.2 Thực hiện một ví dụ lập lịch thi trên chương trình demo 71
4.3 Tinh chỉnh và bổ sung chương trình sau thời gian chạy thử nghiệm tại phòng Đào tạo LHU .76

Chương 5. ĐÁNH GIÁ KẾT QUẢ ĐẠT ĐƯỢC
5.1 Đánh giá 77
5.2 Kết luận .78
TÀI LIỆU THAM KHẢO

1.1 0BDẫn nhập
Lập lịch biểu là việc không thể thiếu ở bất kì tổ chức nào hoạt động trong xã hội loài người. Từ ngàn xưa, con người đã thực hiện việc lập kế hoạch bằng cách ghi chép bằng tay các kí hiệu hay số liệu, thông tin trên vách đá, trên tre, trên vải và trên giấy, có thể gọi chung là trên sổ sách.
Ngày nay, cùng với tiến bộ xã hội, khoa học máy tính đã có những bước tiến dài, đem lại sự tiện lợi và hiệu quả kinh tế cao trong rất nhiều lĩnh vực từ công nghiệp cho đến đời sống. Việc lập lịch biểu bắt đầu có sự giúp sức của máy tính, giúp ghi nhớ các số liệu lớn một cách dễ dàng và thuận lợi hơn so với ghi chép bằng tay trên sổ sách, nhất là khi vận chuyển. Nhiều phần mềm máy tính có chức năng hỗ trợ lập lịch như MS.Excel, MS.Project, nhưng sự “thiếu thông minh” của chúng vẫn làm cho con người phải tiêu tốn nhiều thời gian cũng như công sức khi lập lịch. Nhu cầu máy tính thông minh như con người trở thành bức thiết.
Các kỹ thuật mạnh mẽ của công nghệ tri thức đã sớm cho ra đời những cỗ máy có trí thông minh nhân tạo dạng hệ chuyên gia như máy chẩn đoán bệnh, máy dự báo thời tiết, hoặc dạng hệ tư vấn hỗ trợ con người ra quyết định trong nhiều tình huống vô cùng hữu ích. Từ đó, những kỹ thuật này cũng hỗ trợ việc lập lịch biểu trên máy tính trở nên dễ dàng hơn.
Thông thường, tại một trường đại học, nhu cầu có một công cụ hỗ trợ tự động lập lịch biểu hết sức cần thiết cho hai việc cụ thể: lập lịch giảng dạy (hay lịch công tác) và lập lịch thi. Mặc dù bức thiết là thế, song, đến nay, hầu hết các trường vẫn chưa tìm thấy một công cụ nào thực sự thỏa nhu cầu ngoại trừ một số ít trường đã tự xây dựng công cụ lập lịch thi cho riêng mình. Tùy vào đặc thù và nhu cầu của mỗi trường mà công cụ này được xây dựng bằng những kỹ thuật khác nhau nhằm đạt kết quả càng gần với mong muốn càng tốt.Một số kỹ thuật thường được dùng để giải quyết bài toán lập lịch thi như giải thuật di truyền, leo đồi,
luyện thép, Thế nhưng, qua khảo sát cho thấy khi sử dụng riêng lẻ một trong các kỹ thuật trên kết quả của bài toán vẫn còn nhiều hạn chế. Vì thế, con người vẫn hướng đến một giải pháp sao cho kết quả bài toán lập lịch thi “tối ưu” hơn nữa.

1.2 1BBài toán lập lịch thi tại Trường Đại học Lạc Hồng (LHU)
1.2.1 Thực trạng
Đặc thù tổ chức, cơ sở
- Chương trình đào tạo từ niên chế đang chuyển dần sang tín chỉ.
- Một năm học có hai học kì. Mỗi học kì có ít nhất từ 3 kì thi tập trung cấp độ toàn trường trở lên: lần I, lần II và giữa kì, .
- Mỗi kì thi có khoảng 120.000 lượt thí sinh tham gia thi khoảng 350 môn khác nhau, trong đó, mỗi thí sinh có thể thi khoảng 7-8 môn.
- Có 5 cơ sở thi nằm cách nhau trong vòng 3 km, chứa tối đa khoảng 90 phòng thi có sức chứa khác nhau (25, 30, 50, 60, 80, 90, 120).
- Một ngày có thể chỉ có tối đa 5 ca thi tương ứng theo các mốc thời gian 7h30, 9h30, 13h00, 15h00, 18h00.
- Bình quân, cần khoảng 2 tháng để chuẩn bị và tổ chức một kì thi.
- Mỗi khoa tự tìm mời cán bộ coi thi (CBCT).