摘 要: 排课是一个涉及了多因素动态组合规划的问题, 其核心是根据现有的教师、教室和时间三类资源，在遵从教学规律的基础上，按照合理分配教学资源的原则，通过最优的排列组合以实现排课的最佳效果。本文结合笔者在排课过程中遇到的一些实际问题进行描述,提出了一些改进思路，并通过对各种排课算法的简单介绍，选取回溯算法作为医学院校排课问题实现的最终算法。
关键词:排课;约束条件;回溯算法
0. 引言
现阶段，随着我国教育体制改革的不断深入、大众化教育阶段的到来，高校招生规模迅速扩大，其课程设置不断向深度和广度发展，教学体制也逐渐由学年制向学分制过渡，加上各个专业课程的上课方式、学生水平以及社会发展等各个方面因素的影响,尤其医学院校专业繁多、课程间逻辑关系强，这些都对高校教务管理提出了更高的要求。而排课是高校教务管理的一项极为重要的工作，也是广大师生最为关心的问题。目前高校课程表的编排工作相对于传统的排课方法有了很大的改进,但现有的排课系统,还或多或少存在着一些问题,需要进一步完善,尤其是亟待解决的排课过程中产生的教学资源的冲突问题,更是重中之重,难中之难。
1. 排课相关问题
排课是一个涉及多种因素的动态组合规划的问题,它虽是数学上的时间与空间的组合问题，但排课过程却是人的主观因素作用下的人文决策过程[1]。排课的核心是根据现有教师资源、教室资源和时间资源，如何使排课结果最佳，其实质就是将班级、教师、课程、教室这些教学资源安排在一周内某一不发生冲突的时间,且要满足一定的约束条件,保证课表在时间和空间的分配上符合共性和个性的要求,并尽量达到全局最优。在排课过程中,不仅要解决课程安排对时间和空间资源的有效利用并避免相互冲突(硬约束条件),还需要考虑课程教学效果、满足教师特殊要求等多项优化指标(软约束条件) [2]。
排课时，要尊重教学规律，合理分配教学资源。在排课过程中，主要考虑三类资源：教师资源、教室资源以及时间资源。教师资源包括所有代课教师，主要由各个教研室自行安排，多数情况下，在进行教学任务安排时，已经人为考虑了教师和课程之间的固定联系。教室资源是指现有可用的教室以及实验室，对于医学院校还包括见习医院等特殊教室资源。时间资源是指允许可用的时间段，此外还需要考虑不同时间段的不同课程的上课效果。
排课通常要满足的硬约束条件有:
(1)同一教学班的学生在同一时间只能安排一门课程。
(2)同一教师在同一时间只能安排一门课程。
(3)同一教室在同一时间只能安排一门课程。
(4)同一时间安排的课程总数不能大于所能提供的教室总数。
(5)每门课程参加学习的总人数不能大于所安排教室的座位数。
(6)一个教学班不能重复安排同一门课程。
(7)某些课程需要特殊教学场地譬如多媒体、计算机机房、听力教室、实验室、病房、门诊等。
(8)某门课程只能排在某个时间或在某个时间不能排课。
这是排课过程中首先必须满足的条件。此外,如下一些软约束条件如果能满足的话也应该尽量满足,但是优先级别比上面的约束条件低一级:
(1)一门课程周学时不是很多时,在同一天内不得重复，在一周内的上课时间尽可能合理分布。
(2) 体育课最好不要安排在一天中的第1、2节,并且在体育课后最好不要再安排其它课程。
(3) 见习课必须考虑各个附属医院的教学资源的承教能力。
(4) 必须考虑合班课和单双周上课的情况。
(5) 某些教师的合理的特殊要求,排课时应尽量满足。
(6) 同一个教学班连续的两门课之间尽可能减少教室更换，或就近安排。
(7) 同一课程的不同讲次尽可能安排在同一教室，尽量隔一天以上安排。
(8) 学生每天的必修课安排尽可能趋于平衡；
最后，笔者总结排课实践过程中的经验和教训，提出的一些改进的地方:
(1)对教学任务中的课程进行合理安排。首先根据课程的内在逻辑关系优先安排医学基础课程和约束条件较多的课程,然后将周课时多的或者有实验、见习课的课程优先安排,最后再按照课程的重要性进行课程之间顺序的排列。
(2)对教室进行合理分配。首先分类,比如多媒体教室、计算机机房、语音教室、普通教室等,然后按照教室容量的大小从小到大进行排序,即安排一个课程是根据班级人数优先安排小教室，以保证人数较多的合班课程的教室使用。
(3)对见习或实验课程合理安排。即实验课或是见习课要安排在理论课之后，即理论课讲过该内容以后才能安排相应内容的实验课或是见习课。
(4)对教师的合理安排。即优先安排带课多、约束条件多的教师。
(5)对班级进行合理排序,首先班级人数多的优先排序,课程多的班级在前面优先排课。
总之，排课实际上是按照课程表上的教学任务,选取排序好的课程任务,安排教师表中排序好的相应的教师放在空闲的排好序的教室表的教室在某一个时间片给某一个班级上课[3]。
排课时若没有周密的考虑，所排出的课表势必影响师生的工作学习情绪，甚至影响教学质量，造成教学事故。因此，应该在遵循教学规律、统筹全局的基础上选择合适的方法进行排课的实际操作。
2. 排课系统和算法的选择
2.1 排课系统
目前，高校里所使用的教务管理系统主要有三种版本：清华大学计算机与信息管理中心开发的“UEAS高校教务管理系统”、湖南青果软件有限公司开发的“KINGOSOFT高校教务网络管理系统”和杭州正方电子工程有限公司开发的“正方现代教务管理系统”。这三个系统都有相应的排课功能，它们有很多相同、相近、相似的地方，但也各有各的特点，各高校可根据本校需求进行选择。
2.2 算法
1975年S.艾温(Even.S)证明了排调课问题是NP—完全的(完全不确定多项式)[4]，宣布了这一时空组合问题的学术地位和难度[5]。因此,回溯算法的空间需求为一个常数,即从开始节点起最长路径的长度，但它的时间复杂度较大。
该算法比较符合医学院校排课要求,如果约束条件设置好,几个关键的表能够排好序,时间复杂度可以相应的减少，而且必要时可以和其它的算法结合使用，以达到更优效果。
3. 结束语
当今社会，高校的招生规模继续扩大,社会环境也在不断变化,必然会对高校的教学运行产生一定的影响，排课过程中也会出现一些新的问题和新的约束条件。目前各个高校也都在结合本校具体情况，探索、开发适合本校的排课方法，我们的排课技术将不断成熟,将来必然会有更多新的、成熟的算法出现, 而多种算法相结合进行排课的优势得到了更多的认可。因此,笔者认为，把多种算法结合在一起排课将会收到更好的效果。
参考文献:
[1]周建新,王科俊,王文武,等.课表编排专家系统[J].计算机应用,2000,20(5):76-78.
[2]张晶，李广军，唐远翔.智能排课算法综述[J]，长春大学学报,2009,19(8),38-41
[3]许荣泉,秦小屿.排课问题的研究与改进软件导刊[J]2010，9（3）:66-67网址：http://www.cnkikbs.com
[4]Even,S.ItaiandA.Shamir.On the complexity of timetable and multicommodity flow problems[J].SIAMJ.Comput,1976,(5):691-703.
[5]业宁,梁作鹏,董逸生.一种基于遗传算法的TTP问题求解算法[J].东南大学学报:自然科学版,2003,33(1):41-44.
[6]石菁,李洪波.排课算法比较[J].福建电脑,2004(8).
|
