摘要
随着计算机的广泛应用和互联网技术的高速发展,在全国高校中许多教学管理系统相继投入使用。课程编排及课表管理是教学管理的必要组成部分,其课表编排质量直接关系到后继教学活动的开展,因此排课功能在整个教学管理中占有重要地位。
排课问题已经被证明是一个NP完全问题,因此,在实际项目的研发中,开发出符合要求的排课系统有一定难度。本论文分析了远程教学支撑平台的教务流程的特点以及高等学校制定课表的原则,对排课需求进行了分析、描述,建立了排课问题的组合优化数学模型。
论文对各种排课算法进行了研究。根据实际需求,最终提出了一个比较符合实际情况的基于贪婪策略的排课问题求解算法——ICSAG(Intelligent Curricular Scheduling Algorithm based on Greedy Method)算法。
论文给出了ICSAG算法的详细设计方法,并编程加以实现。最后对此算法进行了测试,测试表明此算法能够从实际的排课情况出发,有效地满足了事先规定的各种排课限制条件,达到了实际应用需求。
根据智能课表编排系统的需要,将这个ICSAG算法应用于实际系统开发中,实现了一个Web环境下的智能课表编排系统。经过测试,排课结果和用户使用性能达到设计要求。
最后,在智能排课系统的工作基础上,初步实现了一个选课系统。其选课操作能够基于排课结果正确执行,选课系统与排课系统保持了数据的一致性,保证了操作的可靠性。
With the widely use of computer and rapid development of internet, many teaching management systems have been successfully used in domestic universities. The curriculum scheduling system is a sub-module of education management system, and the quality of the course timetable will directly relates to other tasks of teaching management, so the curriculum scheduling task plays a key role in the teaching management work.
As the course timetable problem had been proved to be a NP completeness category problem, to make out a satisfactory curricular arranging system is a difficult task. This paper analyzed the characteristics of the teaching management flow and principles of university curricular scheduling, and analyzed, described the requirements of the curricular scheduling, and then created the combinatorial optimization model of the course timetable problem.
This paper researched many kinds of algorithms about course timetable arranging. Finally I brought out an algorithm based on the greedy method that can fulfill the real situation– the ICSAG (Intelligent Curricular Scheduling Algorithm based on Greedy Method)algorithm.
In this paper, I described the design of the ICSAG algorithm in detail, and then implemented it with programming language, and finally tested it. The result of the testing work proved that: this algorithm gets start from the real situation of curricular scheduling, and can fulfill all the restrictions brought up previously. It can achieve the level of real application requirement.
According to the real requirement of the intelligent curricular scheduling system, I applied the ICSAG algorithm to the system project and implemented an intelligent curricular scheduling system based on Web environment. After testing, the course arranging result and the performance of the system all achieved the design target.
Based on the work of the intelligent curricular scheduling system, I implemented a preliminary course-selecting system. The operation of course-selecting can run correctly with the course arranging result. The curricular scheduling system and the course-selecting system can assure the data consistency and the reliability of the users’operations.
引文
1 Cotlieb C. C. The Construction of Class-teacher Timetable [C]. Proc. IFIP Congress. 1962:73~77
2 Even S, Itai A, Shamir A. On the Complexity of Timetable and Multieommodity Flow Problems [J]. SIAM Journal on Computing. 1976,5(4) :691~703
3 昌玉剑.计算机辅助排课系统的设计与实现[D].北京科技大学硕士学位论文.2005
4 张晓瑜 课程表编制研究[D] 华东师范大学硕士论文 2002
5 A. Schaerf. A Survey of Automated Timetabling [J]. Artificial Intelligence Review, 1999(13):87~127
6 Mike W. Subcost. Guided Experience with Timetabling Problems [J]. Journal of Heuristics. 2001(7):251~260
7 A. S. Asratian, D. de Werra. A Generalized Class-Teacher Model for Some Timetabling Problems [J]. European Journal of Operational Research. 2002(143):531~542
8 Tim B. Cooper, Jeffrey H. Kingston. The Complexity of Timetable Construction Problems [C]. Proc.ICPTAT95. 1995:183~295
9 Murphy J, R. Suter. School Scheduling by Computer - the story of GSAP [J]. Educational Facilities Labs. Inc. New York. 1964,12: 128~141.
10 E. D. Barraclough. The Application of a Digital Computer to the construction of timetables [J]. The Computer Journal. 1965,8(2):136~146
11 Ferland J, A. Roys. Timetabling Problem for University as Assignment of Activities to Resources [J]. Computers and Operations Research. 1985,12(2):207~218
12 D. de Werra. An Introduction to Timetabling [J]. European Journal of Operational Research. 1985(19):151~162.
13 Wood D. C. A Technique for Coloring a Graph Applicable to Large Scale Timetabling Problem [J]. Computer Journal. 1969(12):317~319
14 G. A. Neufeld and J. Tartar. Graph coloring conditions for the existence of solutions to the timetable problem [J]. Communications of the ACM. 1974,17(8):450~453.
15 孙建平,梅晓勇,肖政宏,史忠植 关联规则在高校智能排课系统中的应用[J] 计算机应用. 2002,12(5):37~39
16 韩雅鸣,肖玉巍,张志军 关联规则挖掘在高校排课过程中的应用[J] 微计算机应用 2007,1(1):54~57
17 李娟,何福保,徐远纯 基于关联规则的排课系统[J] 福建电脑 2006,5(5):25~36
18 吴金荣 求解课程表问题的分支定界算法[J] 运筹与管理. 2002,11(1):17~22
19 王枯民,赵致格 排课表问题中的分组优化决策算法 [J] 控制与决策 1999,14(2):109~114
20 彭涛,李建国,白峰杉 排课问题分组优化决策中的 CourseRank[J] 高校应用数学学报A 辑 2006,2(1):31~36
21 雷涛,王静,徐岩 基于分组优化和矩阵运算的自动排课算法[J] 兰州交通大学学报(自然科学版) 2006,6(3):97~99
22 胡小兵,鲁宏伟 基于模糊专家系统的排课系统关键技术的研究[J] 长沙电力学院学报(自然科学版) 2001,11(4):26~28
23 董启明 专家系统在自动排课中的应用与研究[D] 长春理工大学硕士学位论文 2006
24 佟林 基于专家系统的排课软件的研究与设计[D] 哈尔滨工程大学硕士学位论文 2004
25 张海涛 高等学校计算机排调课专家系统研究[D] 辽宁工程技术大学硕士学位论文 2005
26 黄干平,姚自珍,张轶静 使用模拟退火算法解课表问题[J] 武汉大学学报(自然科学版) 2000,4(5):559-561
27 梁立,肖飞,李志虹 基于模拟退火的排课算法[J] 云南师范大学学报 2006,11(6): 28~37
28 A. Colorni, M. Dorigo, V. Maniezzo. A Genetic Algorithm to Solve the Timetable Problem [J]. Politecnico di Milano, Italy, 1992:90-060
29 Lars Vestergaard Kragelund. Solving a Timetabling Problem Using Hybrid Genetic Algorithms [J]. Software-Practice and Experience. 1997:1121~1134
30 杨宇 高校排课系统理论研究与开发—遗传算法在课表问题中的应用[D] 北京理工大学硕士学位论文 2003
31 Chu P C, Beasley. A Genetic Algorithm for the Generalized Assignment Problem [J]. European Journal of Operation. 1995
32 Luan F, Yao X. Soving Real-world Lecture Room Assignment Problems by Genetic Algorithm [J]. Complexity International - An Electronic Journal of Complex Research. 1996,3:187~192
33 郑月锋 遗传算法在求解时间表问题中的应用研究[D] 浙江工业大学硕士学位论文 2005
34 Saafai D, Sigeur O. Incorporating Constraint Population in Genetic Algorithm for University Timetable Planning [J]. Engineering Applications of Artificial Intelligence. 1999(13):241~253
35 Ho sung C. Lee. Timetabling Highly Constraint System via Genetic Algorithm [D]. master degree paper of Department of Mathematics College of Science University of the Philippines Diliman. 2003
36 Michael, Francis, Gorman. An Application of Genetic and Tabu Searches to the University Curricular Arranging System [J]. Annals of Operation Research. 1998(78):51~69
37 International Timetabling Competition Website [EB/OL]. http://www.idsia.ch/Files/ttcomp2002/oldindex.html
38 P. A. Kostuch, Timetabling Competition - SA-based Heuristic [EB/OL]. http://www.idsia.ch/Files/ttcomp2002/kostuch.pdf
39 Jean Franois Cordeau, Brigitte Jaumard, Rodrigo Morales. Efficient Timetabling Solution with Tabu Search [EB/OL]
40 Yuri Bykov. The Description of the Algorithm for International Timetabling Competition [EB/OL]. http://www.idsia.ch/Files/ttcomp2002/bykov.pdf
41 Edmund Burke, Yuri Bykov, James Newall, Sanja Petrovic. A Time-Predefined Local Search Approach to Exam Timetabling Problems. IIE Transactions on Operations Engineering. 2004(36):1~19
42 The 6th International Conference on the Practice and Theory of Automated Timetabling [EB/OL]. http://patat06.muni.cz/intro.html
43 唐洪英,周敏 基于分层分次贪心算法的排课系统的设计与实现[J] 微计算机信息 2006(12): 237~240
44 聂小东 基于贪婪算法的排课系统的研究与实现[D] 广东工业大学工学硕士学位论文 2006
45 梁立,陈玉华,徐敏 基于贪心法的排课算法[J] 云南师范大学学报 2005,5(25):9~16
46 王伟,余利华 基于贪心法和禁忌搜索的实用高校排课系统 [J] 计算机应用 2007,11(21):2873~2876
47 曾光清 贪婪算法在高校排课系统中的运用 [J] 福建金融管理干部学院学报 2007(6):49~45
48 聂小东,李振坤,陈平华 基于贪婪算法的排课系统的探讨与实现[J] 现代计算机 2007,11:109~112
49 J. CSIMA, C. C. GOTLIEB Tests on a Computer Method for Constructing School Timetables[C] Communications of ACM 1994,3(7) 160~167
50 Sueychyun Fang, University Course Scheduling System(UCSS) - A UML Application with Database and Visual Programming [C] Consortium for Computing Sciences in Colleges.2005,6:160-169
51 M.Dimopoulou, P.Miliotis. An Automated University Course Timetabling System Developed in a Distributed Environment. A Case Study European Journal of Operational Research 2004:136-147
52 施裕琴 基于.NET 框架网上选排课系统的研究与设计[D] 天津大学硕士学位论文 2006