摘要
排课问题在分类上,可以归为资源分配问题,资源分配就是必须以满足所有限制为前提的情况下,将有限的资源分配给每一个活动。满足资源限制与排课规则等硬性限制的课表,只能算是可行的课表;若要提高课表的满意度则必须要考虑更多的软性限制,也就是每个教员的授课偏好。但在实际上不可能完全满足每一个教员的需求,比较可行的解决方案是让课表可以满足所有的硬性限制,并且尽可能满足软性限制。本研究在解决方案中出除了考虑硬性限制以确保课表的可行性外,还考虑排课问中的软性限制。本研究针对排课过程当中安排资源的原则,以及课程、教员、教室与教学班之间相互的限制关系建立一套排课问题的Constraints Satisfaction Problems(CSP)模型。然后利用ILOG Scheduler与ILOG Solver工具在C++Builder 5.0环境下设计一个有效的运算解决方法。
In the classification the arrangement of the curriculum can be defined as the distribution of the resource that is distributing the limited resource to every action under the premise of satisfying all of the constraint.
Satisfying resource constraint and the rule of the arrangement of the curriculum is just a feasible schedule. If want to improve the satisfaction of the schedule, soft constraint must be thought of which is the hobby of every teacher.
But in fact, satisfying every teacher's hobby completely is impossible, the more feasible solution is to make the schedule to satisfy the hard constraint and satisfy the soft constraint as far as possible.
The paper proposes a solution that not only thinks of the hard constraint to assure the feasibility of the schedule, but also thinks of the soft constraint in the schedule. According to the principle of the arrangement of the resource of the schedule and the constraint relation between curriculum, teacher, classroom and class, establishes a model of the arrangement of the curriculum called CSP(Constraints Satisfaction Problems).
And then designed a effective solution under the environment of C++ Builder 5. 0 with the tool of ILOG Scheduler and ILOG Solver.
引文
[1]花鹏飞.课程表问题的概念分析[EB].中国科技论文在线网.:(HTTP://www.paper.edu.cn),2006-10-8
[2]花鹏飞.课程表问题的数学分析[EB].中国科技论文在线.:(HTTP://www.paper.edu.cn),2006-10-9
[3]叶杰荣.应用限制规划方法来探讨即时排课问题[ED].中国科技论文在线,:(HTTP://www.paper.edu.cn),2006-11-2
[4]廖圣扬.应用限制规划方法求解军事院校排课问题[ED].中国科技论文在线,:(HTTP://www.paper.edu.cn),2006-11-2
[5]黄万华.高校教务管理系统的设计与实现[J].计算机与数字工程,2004第3期
[6]姜英新.约束满足问题求解及ILOG SOLVER系统简介[J].吉林大学学报,2002第1期
[7]陶华亭.基于图论方法的自动优化排课模型研究[J].微计算机信息.2005第27期:P.129-131
[8]An Introduction to Constraint Satisfaction Programming.generation5.2006-4
[9]业宁,梁左鹏.一种基于遗传算法的TTP问题求解算法[J].东南大学学报(自然科学版),2003第1期:P.41-44
[10]BURKE E K.Recent research directions in automated timetabling.European Journal of Operational Research,2002.140.02:P.266-280
[11]吴志斌,孙晓安.回溯算法与计算机智能排课[J].《计算机工程》.1999第3期:P.79-80
[12]王晓东.计算机算法设计与分析[J].《北京:电子工业出版社》.2001:P.83-110
[13]陈冬亮.排课的数学模型和算法在教务管理系统中的应用研究[J].《电脑知识与技术(学术交流)》2006第6期
[14]郝瑞,段富.排课管理系统的设计与实现[J].《科技情报开发与经济》2006第2期
[15]韩承双,张春梅.自动排课系统迭代算法设计与实现[J].合肥学院学报(自然科学版),2005第3期
[16]李润辉,兴龙.对高校的计算机专业排课算法的分析[J].《福建电脑》,2004第3期:P.72-73
[17]陈谊,张国龙.基于优先级自动排课算法PCSA的设计与实现方案[J].北京工商大学学报(自然科学版),第20卷第2期
[18]吴志斌,陈淑珍.回溯算法与计算机智能排课[J].《计算机工程》,1999第25卷第3期:P.79-80
[19]陈源,史忠植.约束满足问题求解途径之比较与分析[J].计算机科学,1998第25卷第1期:P.8-12
[20]谭浩强,张基温.程序设计与开发技术[M].北京清华大学出版社,1991:P.56
[21]秦笃烈.程序设计技术与开发[M].海洋出版社,1990:P.120
[22]陈本庆,马永强.改进型回溯法在高校排课中的应用[J].成都信息工程学院学报,2003第18卷2期:P.150-154
[23]陈洁.学校教务部门排课问题的数学模型及算法[J].管理信息系统,1999第3期:P.52-56
[24]郑中华,赵卫东.高校排课问题的模型与求解[J].山东科技大学学报(自然科学版),2004第23卷第4期:P.111-113
[25]陈传波.模拟退火算法在排课中的应用[J].武汉船舶职业技术学院学报,2003第2卷第3期:P.22-24.
[26]唐勇,王玲.基于遗传算法的排课系统[J].计算机应用,2002第22卷第10期:P.93-94,97
[27]田岭.大学自动排课算法设计与实现[J].教育信息化,2006年7月,(总第136期):P.44-P46
[28]晓寒.软件组件帮助企业提高运作效率—访ILOG公司首席运营官Bounthara ING[N].《世界电信》2004第17卷5期:P.60-60
[29]B.Smith,K.Stergiou.ILOG,S.A.ILOG Solver 6.0:User's Manual[S].2003.[3]:P7-21
[30]Chiu Wo Choi,Lee.Controlling salinity in a potable water supply system using a constraint programming approach[H].Tools with Artificial Intelligence,2005.ICTAI 05.17th IEEE International Conference on Volume,Issue:14-16