论文部分内容阅读
中图分类号：G47 文献标识：A 文章编号：1006-7833（2012）02-000-02
摘 要 排课问题及相关算法是一种基于动态规划思想和优先级编排的混合排课算法。排课算法分为三个阶段：课程归档阶段、贪心求解阶段、回溯求解阶段，此算法可根据教室、教师、时间和班级的约束关系，根据所设定的优先级顺序完成一次性扫描排课，尽量避免冲突并调整冲突。
关键词 排课 算法 动态规划思想 冲突 回溯
一、课程表编排问题
排课问题是一个涉及多种因素的动态组合规划问题，它要保证各种教学资源不产生冲突，并且要满足教学资源各方面的约束条件。教学资源主要包括课程、教师、教室、时间。排课问题的求解过程就是对任何课程、班级、教师、教室安排出一个相同的空闲时间，在排课时不能发生冲突，同时遵守一些约束条件。所谓冲突就是将上不同课程的两个或多个班排成了同一时间或同一教室，或在同一时间为一个教师安排了多门课程等等。排课流程一般是：首先，各院系将各自的新学期课程表、任课教师情况、班级课程安排情况的数据录入排课系统，然后，排课系统根据本学校的教室情况以及各种约束条件进行排课。
二、课程表编排问题的数学模型
班级集合：B={B1，B2，B3，B4，…，Bi，…，Bu)；Bi={bi1,bi2，…，bij，…，biv }，其中bij表示单个自然班级，Bi表示专业和年级相关的实际班级，它可以是一个自然班，也可以是多个自然班。课程集合：C={C1，C2，C3，C4，…，Ci，…，Ck}；教师集合：S={Sl，S2，S3，S4，…，Si，…，Sl}；教室集合：R={R1，R2，R3，R4，…，Ri，…， Rk，…，Rm}；其中，Rk表示具体教室，属性包括：楼号、序号、大小(以容纳人数为衡量标准)、是否多媒体或语音室等等。时间集合：T={tl，t2，t3，t4，…，ti，…， tn}；时间tn包含周次(Z，Z∈[l，26])，星期(W，W∈[1，7])，节次(J，J∈[1，5])，一般课程是两节连排，节次中1表示1、2节，2表示3、4节以此类推。Z、W、J均可根据实际情况的需要确定取值范围[1]。
系统执行课程编排之前，(B×C×S)都是一一对应的任务单元(task)，排课的目的就是为每一任务单元分别安排相应的时间与地点(R×T)，同时必须满足一定的约束条件。
三、排课算法研究
课程表编排实质是为课程、班级、教师安排一个合理的时间和地点，故将课程、班级、教师看作任务单元，用三元组表示T（c,b,t）,其中c代表课程，b代表班级，t代表任课教师；课程表编排的目的是为T（c,b,t）固定一个合理的时间和地点进行正常的教学活动。考虑到单一的算法无法适应多样化的排课需求，因此此排课算法融入了贪心、局部搜索、回溯算法等多种算法，以期望在面对不同排课需求时，排课算法均能够较好的完成排课。
（一）课程归案阶段
该阶段主要是对课程进行预处理，为每一个任务单元确定优先级。任务单元的优先级由三个方面因素决定：首先是课程影响范围的大小。课程影响范围越大优先级高，反之，优先级低。其次是任课教师担任的课程数。在第一因素相同的前提下，教师担任的课程数越多，优先级越高。第三是任课教师担任的班级数。在第一因素和第二因素相同的前提下，教师担任的自然班越多，优先级越高。
（二）贪心求解阶段
贪心算法采用逐步构造最优解的方法，它对很多问题产生整体最优解，即使不能得到整体最优解，也能找到最优解的很好的近似解。更关键的是，贪心算法的时间复杂度很低，在处理大规模数据时速度很快，非常适合用来处理排课问题。
贪心求解阶段，设置一个评估函数f(i,j,k)。计算将任务单元i安排到第j天的第k次课的函数值（一天中，第1次课为的1,2节，第2次课为3,4节，以此类推，第5次课为9,10节）。根据课程表编排的约束条件，令C(i,j,k)表示将任务单元i安排到第j天第k次课是否满足所有的硬性约束， ；令r(i,j,k)表示满足软性约束的条件数，r(i,j,k)=a表示将任务单元i安排的第j天第k次课满足a条软性约束；令bcc表示正在安排的任务单元对应的班级第j天已安排的课程数，初始值为1，则f(i,j,k)定义为： ，利用计算评估函数所得的函数值，将课程安排在函数值大于0且最大的第j天第k次课。如果贪心求解成功，则本次排课成功；反之，贪心求解失败，将此课程抛入死锁队列。
使用贪心算法极大的提高了大部分课程的排课速度，设计合理的评估函数也使自动排课的结果较为合理，具有较好的实际意义。
（三）回溯求解阶段
虽然贪心求解能够合理安排大部分课程，但是由于贪心算法只考虑局部最优而没有考虑全局最优，因此很可能有一些课程无法通过贪心策略进行安排，而有时通过对已安排课程的微调是可以完成对这些课程的安排的。回溯算法就是为了处理这种情况而设计的。
回溯算法的基本原理是通过递归和回溯的方式来寻找增广路径，寻求死锁课程安排时间，同时通过控制递归的最大深度来减少搜索的次数，避免了完全搜索速度慢的问题。回溯算法根据用户约束，依此枚举每一个上课时间，尝试调整当前课程a至新的时间从而为死锁课程让开时间。如a没有无法通过寻求新的时间来完成本次要求，那么开始进入递归阶段开始尝试为调整b为a让开时间。依次调整后最终至c寻找出通路，然后c调整至新的时间，b、a依次调整后，死锁课程安排完毕[2]。
回溯搜索算法极大地弥补了贪心算法无法安排课程的问题，虽然算法占用时间较多，但是该算法的加入使得自动排课的正确性得到很大提高，减轻了后期手动排课的压力。
四、冲突回溯算法设计
排课问题中出现的冲突问题往往采用回溯方式进行处理。首先，针对已经安排的任务单元进行重新编排，然后，尝试将引起冲突的任务单元重新排入课表，最终达到解决冲突问题的目的[3]。具体如图1所示。
图1 回溯结构树
Tc表示产生冲突的某个任务单元，当发生冲突时从此节点向前产生回溯，对前面已经编排就绪的任务单元，即ta，tb，tc，td进行重新编排。任意选择一个任务单元ta编排并检测重新编排后与其它任务单元发生冲突情况，同时将tc排入课表，若冲突或Tc仍然不能排入，则以ta为新的节点，进一步向前回溯，对前面已排好的任务单元(tc，tf)进行重新编排。选择其中一个任务单元tf编排并检测重新编排后与其它任务单元发生冲突情况，同时将tc、ta排入课表，若冲突或tc、ta仍然不能排入，则以tf为新的节点向前回溯。依此类推，向前回溯直到解决冲突为止。
这是一种自顶向下的回溯方式，从根结点出发以深度优先的方式搜索整个解空间。这种搜索方式采用深度优先有界启发式。事先需要设置搜索深度为防止无限制向前搜索，从而造成计算机锁死。当超过这个深度，还未找到解决办法时就需要返回进行重新选择另一组进行冲突解决。回溯处理过程本质是一个在若干有限集合构成的笛卡儿集内，选取一个满足一定条件的元素的有限穷举过程。若找不到满足条件的元素则回溯失败。造成回溯失败的原因主要有①时间编排设置过于理想化；②部分班级或者教师的课程编排相对过于集中；③合班编排不合理；④教室资源相对不足。针对以上4个原因，可以在实际排课过程中通过优化配置资源来进行解决。
五、冲突回朔算法实现
系统排课的初期阶段无论是时间还是教室资源都相对比较充足，发生冲突的几率较少，随着编排的逐渐进行，时间和教室资源越来越紧缺，可供选择的越来越少，此时发生冲突的几率迅速提高。当发生冲突的时候需要向上回溯至离发生冲突最近的一个编排成功的任务单元，并完成重新编排直至无冲突发生为止。回溯策略的处理方法按照选择编排任务单元方式的不同可以分为三种，具体情况如下：
（一）直接回溯[5]
将已经编排好的课表的任务单元由后向前逐一重排。每重排一个任务单元就试探将其后所有的任务单元重排直到将引起冲突的任务单元排入课表为止，其特点是方法简单、效率不高，因此，在实用算法中一般不宜使用。
（二）班级相关回溯
将已排入课表的任务单元与引起冲突的任务单元的上课班级相关的任务单元由后向前逐一重排，每重排一个任务单元就试探将其后所有的任务单元重排直到将引起冲突的任务单元排入课表为止。
（三）教师相关回溯处理
将已排入课表的任务单元与引起冲突的任务单元的教师相关的任务单元由后向前逐一重排，每重排一个任务单元就试探将其后所有的任务单元重排直到将引起冲突的任务单元排入课表为止。
六、结论
本文研究的是基于运筹学中的动态规划思想的优先级自动排课调度算法，其中重点讲解了回溯算法解决冲突问题。要想实现排课，还需要把其他相关算法进行设计与实现，但是已不是重要问题之所在。
参考文献：
[1]王健,董改芳,许道云.基于遗传算法的自动排课系统.青岛:中国计算机学会.2003.
[2]Thomas H Cormen, Charles ELeiserson, Ronaldl Rivest, et al.算法导论.北京:高等教育出版社.2002:664-669.
[3]任曦平,王新房,王煜.基于WEB的选修课管理系统的设计与实现.微电脑应用.2001.17(9):26-28.
[4]程国忠,张世禄.三个典型问题的回溯算法.四川师范学院学报(自然科学版).2000.21(2):187-191.
[5]王岩冰,郑明春,刘弘.回溯算法的形式模型.计算机研究与发展.2001.38(9):1066-1079.
摘 要 排课问题及相关算法是一种基于动态规划思想和优先级编排的混合排课算法。排课算法分为三个阶段：课程归档阶段、贪心求解阶段、回溯求解阶段，此算法可根据教室、教师、时间和班级的约束关系，根据所设定的优先级顺序完成一次性扫描排课，尽量避免冲突并调整冲突。
关键词 排课 算法 动态规划思想 冲突 回溯
一、课程表编排问题
排课问题是一个涉及多种因素的动态组合规划问题，它要保证各种教学资源不产生冲突，并且要满足教学资源各方面的约束条件。教学资源主要包括课程、教师、教室、时间。排课问题的求解过程就是对任何课程、班级、教师、教室安排出一个相同的空闲时间，在排课时不能发生冲突，同时遵守一些约束条件。所谓冲突就是将上不同课程的两个或多个班排成了同一时间或同一教室，或在同一时间为一个教师安排了多门课程等等。排课流程一般是：首先，各院系将各自的新学期课程表、任课教师情况、班级课程安排情况的数据录入排课系统，然后，排课系统根据本学校的教室情况以及各种约束条件进行排课。
二、课程表编排问题的数学模型
班级集合：B={B1，B2，B3，B4，…，Bi，…，Bu)；Bi={bi1,bi2，…，bij，…，biv }，其中bij表示单个自然班级，Bi表示专业和年级相关的实际班级，它可以是一个自然班，也可以是多个自然班。课程集合：C={C1，C2，C3，C4，…，Ci，…，Ck}；教师集合：S={Sl，S2，S3，S4，…，Si，…，Sl}；教室集合：R={R1，R2，R3，R4，…，Ri，…， Rk，…，Rm}；其中，Rk表示具体教室，属性包括：楼号、序号、大小(以容纳人数为衡量标准)、是否多媒体或语音室等等。时间集合：T={tl，t2，t3，t4，…，ti，…， tn}；时间tn包含周次(Z，Z∈[l，26])，星期(W，W∈[1，7])，节次(J，J∈[1，5])，一般课程是两节连排，节次中1表示1、2节，2表示3、4节以此类推。Z、W、J均可根据实际情况的需要确定取值范围[1]。
系统执行课程编排之前，(B×C×S)都是一一对应的任务单元(task)，排课的目的就是为每一任务单元分别安排相应的时间与地点(R×T)，同时必须满足一定的约束条件。
三、排课算法研究
课程表编排实质是为课程、班级、教师安排一个合理的时间和地点，故将课程、班级、教师看作任务单元，用三元组表示T（c,b,t）,其中c代表课程，b代表班级，t代表任课教师；课程表编排的目的是为T（c,b,t）固定一个合理的时间和地点进行正常的教学活动。考虑到单一的算法无法适应多样化的排课需求，因此此排课算法融入了贪心、局部搜索、回溯算法等多种算法，以期望在面对不同排课需求时，排课算法均能够较好的完成排课。
（一）课程归案阶段
该阶段主要是对课程进行预处理，为每一个任务单元确定优先级。任务单元的优先级由三个方面因素决定：首先是课程影响范围的大小。课程影响范围越大优先级高，反之，优先级低。其次是任课教师担任的课程数。在第一因素相同的前提下，教师担任的课程数越多，优先级越高。第三是任课教师担任的班级数。在第一因素和第二因素相同的前提下，教师担任的自然班越多，优先级越高。
（二）贪心求解阶段
贪心算法采用逐步构造最优解的方法，它对很多问题产生整体最优解，即使不能得到整体最优解，也能找到最优解的很好的近似解。更关键的是，贪心算法的时间复杂度很低，在处理大规模数据时速度很快，非常适合用来处理排课问题。
贪心求解阶段，设置一个评估函数f(i,j,k)。计算将任务单元i安排到第j天的第k次课的函数值（一天中，第1次课为的1,2节，第2次课为3,4节，以此类推，第5次课为9,10节）。根据课程表编排的约束条件，令C(i,j,k)表示将任务单元i安排到第j天第k次课是否满足所有的硬性约束， ；令r(i,j,k)表示满足软性约束的条件数，r(i,j,k)=a表示将任务单元i安排的第j天第k次课满足a条软性约束；令bcc表示正在安排的任务单元对应的班级第j天已安排的课程数，初始值为1，则f(i,j,k)定义为： ，利用计算评估函数所得的函数值，将课程安排在函数值大于0且最大的第j天第k次课。如果贪心求解成功，则本次排课成功；反之，贪心求解失败，将此课程抛入死锁队列。
使用贪心算法极大的提高了大部分课程的排课速度，设计合理的评估函数也使自动排课的结果较为合理，具有较好的实际意义。
（三）回溯求解阶段
虽然贪心求解能够合理安排大部分课程，但是由于贪心算法只考虑局部最优而没有考虑全局最优，因此很可能有一些课程无法通过贪心策略进行安排，而有时通过对已安排课程的微调是可以完成对这些课程的安排的。回溯算法就是为了处理这种情况而设计的。
回溯算法的基本原理是通过递归和回溯的方式来寻找增广路径，寻求死锁课程安排时间，同时通过控制递归的最大深度来减少搜索的次数，避免了完全搜索速度慢的问题。回溯算法根据用户约束，依此枚举每一个上课时间，尝试调整当前课程a至新的时间从而为死锁课程让开时间。如a没有无法通过寻求新的时间来完成本次要求，那么开始进入递归阶段开始尝试为调整b为a让开时间。依次调整后最终至c寻找出通路，然后c调整至新的时间，b、a依次调整后，死锁课程安排完毕[2]。
回溯搜索算法极大地弥补了贪心算法无法安排课程的问题，虽然算法占用时间较多，但是该算法的加入使得自动排课的正确性得到很大提高，减轻了后期手动排课的压力。
四、冲突回溯算法设计
排课问题中出现的冲突问题往往采用回溯方式进行处理。首先，针对已经安排的任务单元进行重新编排，然后，尝试将引起冲突的任务单元重新排入课表，最终达到解决冲突问题的目的[3]。具体如图1所示。
图1 回溯结构树
Tc表示产生冲突的某个任务单元，当发生冲突时从此节点向前产生回溯，对前面已经编排就绪的任务单元，即ta，tb，tc，td进行重新编排。任意选择一个任务单元ta编排并检测重新编排后与其它任务单元发生冲突情况，同时将tc排入课表，若冲突或Tc仍然不能排入，则以ta为新的节点，进一步向前回溯，对前面已排好的任务单元(tc，tf)进行重新编排。选择其中一个任务单元tf编排并检测重新编排后与其它任务单元发生冲突情况，同时将tc、ta排入课表，若冲突或tc、ta仍然不能排入，则以tf为新的节点向前回溯。依此类推，向前回溯直到解决冲突为止。
这是一种自顶向下的回溯方式，从根结点出发以深度优先的方式搜索整个解空间。这种搜索方式采用深度优先有界启发式。事先需要设置搜索深度为防止无限制向前搜索，从而造成计算机锁死。当超过这个深度，还未找到解决办法时就需要返回进行重新选择另一组进行冲突解决。回溯处理过程本质是一个在若干有限集合构成的笛卡儿集内，选取一个满足一定条件的元素的有限穷举过程。若找不到满足条件的元素则回溯失败。造成回溯失败的原因主要有①时间编排设置过于理想化；②部分班级或者教师的课程编排相对过于集中；③合班编排不合理；④教室资源相对不足。针对以上4个原因，可以在实际排课过程中通过优化配置资源来进行解决。
五、冲突回朔算法实现
系统排课的初期阶段无论是时间还是教室资源都相对比较充足，发生冲突的几率较少，随着编排的逐渐进行，时间和教室资源越来越紧缺，可供选择的越来越少，此时发生冲突的几率迅速提高。当发生冲突的时候需要向上回溯至离发生冲突最近的一个编排成功的任务单元，并完成重新编排直至无冲突发生为止。回溯策略的处理方法按照选择编排任务单元方式的不同可以分为三种，具体情况如下：
（一）直接回溯[5]
将已经编排好的课表的任务单元由后向前逐一重排。每重排一个任务单元就试探将其后所有的任务单元重排直到将引起冲突的任务单元排入课表为止，其特点是方法简单、效率不高，因此，在实用算法中一般不宜使用。
（二）班级相关回溯
将已排入课表的任务单元与引起冲突的任务单元的上课班级相关的任务单元由后向前逐一重排，每重排一个任务单元就试探将其后所有的任务单元重排直到将引起冲突的任务单元排入课表为止。
（三）教师相关回溯处理
将已排入课表的任务单元与引起冲突的任务单元的教师相关的任务单元由后向前逐一重排，每重排一个任务单元就试探将其后所有的任务单元重排直到将引起冲突的任务单元排入课表为止。
六、结论
本文研究的是基于运筹学中的动态规划思想的优先级自动排课调度算法，其中重点讲解了回溯算法解决冲突问题。要想实现排课，还需要把其他相关算法进行设计与实现，但是已不是重要问题之所在。
参考文献：
[1]王健,董改芳,许道云.基于遗传算法的自动排课系统.青岛:中国计算机学会.2003.
[2]Thomas H Cormen, Charles ELeiserson, Ronaldl Rivest, et al.算法导论.北京:高等教育出版社.2002:664-669.
[3]任曦平,王新房,王煜.基于WEB的选修课管理系统的设计与实现.微电脑应用.2001.17(9):26-28.
[4]程国忠,张世禄.三个典型问题的回溯算法.四川师范学院学报(自然科学版).2000.21(2):187-191.
[5]王岩冰,郑明春,刘弘.回溯算法的形式模型.计算机研究与发展.2001.38(9):1066-1079.