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

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 1BQui 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
- v -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
- vi -
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


Chương 1 GIỚI THIỆU ĐỀ TÀI
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 gia 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).
Đặc thù kỹ thuật
- Lịch thi của mỗi kì thi thường được xếp thủ công trên máy tính chỉ với công cụ hỗ trợ là phần mềm MS.Excel.
- Mỗi lịch thi có khoảng trên 5000 dòng và 14 thuộc tính cần sắp xếp.
- Qui trình để có một lịch thi cho một kì thi được thực hiện như sau: các Khoa tự xếp lịch thi cho các lớp thuộc Khoa rồi chuyển đến Phòng Đào tạo. Phòng Đào tạo nhận và tổng hợp lịch thi từ các Khoa, điền phòng thi lý thuyết và chỉ điều chỉnh lịch thi lý thuyết nếu có “xung đột” giờthi, chuyển phần lịch thi thực hành đến Phòng Điều hành mạng máy tính để xếp phòng máy cụ thể vào lịch thi và điều chỉnh giờ thi phòng máy nếu cần. Sau đó, lịch thi thực hành tại phòng máy được chuyển trả về Phòng Đào tạo, từ đó, Phòng Đào tạo chuyển trả lịch về các Khoa và chờ phản hồi. Trường hợp, Khoa nào cần điều chỉnh lịch thi thì gửi phản hồi về Phòng Đào tạo, và qui trình tương tự trên được lặp lại cho đến khi nào không còn cần điều chỉnh. Thông thường, qui trình này tiêu phí khoảng gần một tháng, thậm chí, trong lúc diễn ra kì thi, lịch thi cũng có thể tiếp tục được sửa đổi bổ sung. Có thể mô tả qui trình trên


TÀI LIỆU THAM KHẢO
TIẾNG VIỆT
[1]. Dương Tuấn Anh, Nguyễn Hữu Hải, Nguyễn Lưu Đăng Khoa (2003), Ứng
dụng giải thuật Tô màu đồ thị vào bài toán xếp lịch thi, đề tài nghiên
cứu khoa học, Đại học Bách Khoa Tp. Hồ Chí Minh.
[2]. Trần Quốc Chiến, Phan Thị Ngà (2009), “Bài toán Tô màu đồ thị và ứng
dụng xây dựng phần mềm xếp lịch thi cho học chế tín chỉ”, Tạp chí
khoa học và công nghệ Đại học Đà Nẵng, 35, tr 85-90.
[3]. Nguyễn Đình Thúc (2002), Trí tuệ nhân tạo Lập trình tiến hóa, NXB Giáo
Dục.
TIẾNG NƯỚC NGOÀI
[4]. Goldberg, D.E (1989), Genetic Algorithms in Search, Optimization and
Machine Learning, Addison-Wesley Press.
[5]. Duong Tuan Anh, Lam Kim Hoa (2004), “Combining Constraint
Programming and Simulated Annealing on University Exam
Timetabling”, Proceedings of 2nd Int. Conf. RIVF’04 Research
Informatics Vietnam-Francophony, Feb. 2-5, Hanoi, pp. 205-210.
[6]. Syswerda G. (1989), “Uniform crossover in genetic algorithms”,
Proceedings of the Third International Conference on Genetic
Algorithms, pp. 2-9.
[7]. John H. Holland (1992), Adaptation In Natural And Artificial Systems, The
MIT Press.
[8]. Dave Kordalewski, Caigu Liu, Kevin Salvesen (2009), Solving an Exam
Scheduling Problem Using a Genetic Algorithm, University of Toronto.
[9]. Mohammad Malkawi, Mohammad Al-Haj Hassan, Osama Al-Haj Hassan
(2008), “A New Exam Scheduling Algorithm Using Graph Coloring”,
The International Arab Journal of Information Technology, Vol.5,
No.1, pp. 80-87.
[10]. Nashat Mansour, Mazen Timany (2007), “Stochastic Search Algorithms for
Exam Scheduling”, International Journal of Computational
Intelligence Research, Vol.3, No.4, pp. 353–361.
[11]. Zbigniew Michalewicz (1999), Genetic Algorithms + Data Structures =
Evolution Program, Springer Press.

Nguồn: http://www.**************/threads/357231-xay-dung-cong-cu-ho-tro-tu-dong-hoa-lap-lich-thi-tai-truong-dai-hoc.html#ixzz2o4iPV543
Thư Viện Điện Tử www.**************