论文部分内容阅读
[摘要] 课表编排实际上就是一个组合规划问题，也就是将时间、课程、教师、教室和学生这几点相结合的过程。排课过程中的首要问题是解决冲突问题，也就是教师、教室和学生之间的安排要合理，不能产生冲突，排课算法的优劣不仅仅在于它是否满足了所有的硬约束条件，还要看它是否能满足尽可能多的软约束条件。满足的软约束条件越多，排课的效果就越好。
[关键词] 排课；冲突；约束；回溯算法
[DOI] 10.13939/j.cnki.zgsc.2015.24.149
为了避免冲突，我们在排课时设定了不同的约束条件，这样才能保证教学T作的正常运行，例如一个教学班在同一时间内只能上一门课，一名教师在同一时间只能给一个班上课（合班课除外）。设计排课算法的重点是对教师、时间、教室、课程等资源进行组合优化，并能够充分发挥各种资源的优势来避免冲突的发生。这样才能取得最好的排课效果。
在实际计算的过程中每个约束条件都会被赋予一个优先级别，优先级别高的约束条件要首先满足，然后再考虑优先级别低的约束条件。在这里，约束条件被分为三类：强制约束条件、特殊优先约束条件和相对约束条件，这三种约束条件的优先级别依次降低。
1 强制约束条件
强制约束的条件在时间上是相同的，即课程安排的时间单元是相同的。在这里强制约束条件包括三个方面的内容：
第一，教师约束，在同一时间，同一教师只能安排一门课程。
第二，班级约束，在同一时间，同一班级只能安排一门课程。
第三，教室约束，在同一时间，同一教室只能安排一门课程。
2 特殊优先约束条件
第一，某一班级或某一教师的上课时间和地点是国定的。比如设置某个教室或实验室在每周某天上午或下午的某节课上某门课程或实验课等等。第二，要预先设定某位教师上哪些课程。第三，某些教师是否有特殊的授课安排或其他特殊要求，这些信息都要存放在一个独立的特殊数据表中特殊优先约束条件的优先级别仅次于强制约束条件。3相对约束条件
排课时强制约束条件是在排课过程中所必须满足的条件，但不是全部条件，在排课过程中还可能产生一些不确定性的因素，我们称之为相对约束条件，这些约束条件很难具体把握，不同的学校和条件下，这些约束条件是不同的，一般我们由一些对学校情况比较了解的老师来制定，在满足了这些相对约束条件之后可以在一定程度上提高教师时间和教室的利用率，从而提高学校的教学效率。
排课系统最关键的部分就是处理排课问题的算法问题。本文采用回溯算法来实现排课，在具体实现过程中将优先级与回溯算法相结合。
3.1 回溯法的前进限制条件
（1） 为了方便老师、学生，同一班级的不同课程课尽量安排在同一个教室授课；
（2） 同一班级的同一门课如果周课时数超过两次时间间隔要尽量长，以免在排课中产生冲突。
（3） 同一教师如果给不同的班级上课，上课时间要尽量分散，不要太集中，以免影响教学效果；
（4） 充分利用教室资源，人数少的班级用容量比较小的教室上课，人数多的班级用容量大的教室上课，以免资源浪费。
3.2 回溯法的回溯条件
首先建立一个按照一定顺序的班级数组列表名称为ClassArrav的类，然后根据不同的顺序，再建立一个科目列表，列表的名称可以白定义，例如SuhjectArray。再按照不同的顺序建立一个关于时间的列表，列表名称白定义，例如PeriodArray。然后从班级列表中取出每类Clas-sArray。然后再从时间列表中取出一段时间，在这里的整个过程是：先尝试在检查最后产生回溯。对于某个类第n个课时：开始从SubjectArray主体中取出插入，选择科目授课教师进行核查，如果检查成功，位列n+1类，如果不通过，换下一个科目取代……；若所有科目变化完仍然无法通过验证，则有是一个错误的，回到第n-1节课，进行课程的重新选择和排列。重复上面的过程。
排课能否成功所排课程在时间上是否合理的关键在于编排课程的先后顺序，这就决定了优先级在排课过程中所占的地位。优先级的确定直接关系到排课的结果，所以对优先级的设置原则做了如下规定：
（1） 根据课程的安排，必修课的优先级别设置要高于选修课，公共课的优先级别设置要高于必修课；
（2） 学校里不同的课程对学生的认知要求不同，课时数也不同，总课时多的课程的优先级别高于总课时数少的课程：
（3） 学校里，并不是所有课程都要求学生学习，有的课程学生可以选择是否选修该门课程，那么就出现了不同课程上课人数不同，上课人数多的课程的优先级别高于上课人数少的课程；
（4） 一个班级在一个学期要求安排若干门课程，但是由于课程的难易程度不同，学校的要求也就不同，所以不同的课程在一学期内的课时数也是不同的，那么一周课时数多的课程的优先级就要高于一周内课时数少的课程；这样才能符合排课的原理，排出的课程才能合理；
（5） 在学校里，有的课程可能不是在任何时间都可以上课的，那么对时间有特殊要求的课程的优先级别高于对时间没有特殊要求的课程；
（6） 在学校里，有的课程可能对场地有特殊的要求，例如试验实训课要求在实验室会实训室上课，那么在授课场地上有特殊要求的课程的优先级高于对场地没有要求的课程；
（7） 有的课程可能还对教师有特殊的要求，那么对教师有特殊要求的课程的优先级高于对教师没有要求的课程的优先级别。
[关键词] 排课；冲突；约束；回溯算法
[DOI] 10.13939/j.cnki.zgsc.2015.24.149
为了避免冲突，我们在排课时设定了不同的约束条件，这样才能保证教学T作的正常运行，例如一个教学班在同一时间内只能上一门课，一名教师在同一时间只能给一个班上课（合班课除外）。设计排课算法的重点是对教师、时间、教室、课程等资源进行组合优化，并能够充分发挥各种资源的优势来避免冲突的发生。这样才能取得最好的排课效果。
在实际计算的过程中每个约束条件都会被赋予一个优先级别，优先级别高的约束条件要首先满足，然后再考虑优先级别低的约束条件。在这里，约束条件被分为三类：强制约束条件、特殊优先约束条件和相对约束条件，这三种约束条件的优先级别依次降低。
1 强制约束条件
强制约束的条件在时间上是相同的，即课程安排的时间单元是相同的。在这里强制约束条件包括三个方面的内容：
第一，教师约束，在同一时间，同一教师只能安排一门课程。
第二，班级约束，在同一时间，同一班级只能安排一门课程。
第三，教室约束，在同一时间，同一教室只能安排一门课程。
2 特殊优先约束条件
第一，某一班级或某一教师的上课时间和地点是国定的。比如设置某个教室或实验室在每周某天上午或下午的某节课上某门课程或实验课等等。第二，要预先设定某位教师上哪些课程。第三，某些教师是否有特殊的授课安排或其他特殊要求，这些信息都要存放在一个独立的特殊数据表中特殊优先约束条件的优先级别仅次于强制约束条件。3相对约束条件
排课时强制约束条件是在排课过程中所必须满足的条件，但不是全部条件，在排课过程中还可能产生一些不确定性的因素，我们称之为相对约束条件，这些约束条件很难具体把握，不同的学校和条件下，这些约束条件是不同的，一般我们由一些对学校情况比较了解的老师来制定，在满足了这些相对约束条件之后可以在一定程度上提高教师时间和教室的利用率，从而提高学校的教学效率。
排课系统最关键的部分就是处理排课问题的算法问题。本文采用回溯算法来实现排课，在具体实现过程中将优先级与回溯算法相结合。
3.1 回溯法的前进限制条件
（1） 为了方便老师、学生，同一班级的不同课程课尽量安排在同一个教室授课；
（2） 同一班级的同一门课如果周课时数超过两次时间间隔要尽量长，以免在排课中产生冲突。
（3） 同一教师如果给不同的班级上课，上课时间要尽量分散，不要太集中，以免影响教学效果；
（4） 充分利用教室资源，人数少的班级用容量比较小的教室上课，人数多的班级用容量大的教室上课，以免资源浪费。
3.2 回溯法的回溯条件
首先建立一个按照一定顺序的班级数组列表名称为ClassArrav的类，然后根据不同的顺序，再建立一个科目列表，列表的名称可以白定义，例如SuhjectArray。再按照不同的顺序建立一个关于时间的列表，列表名称白定义，例如PeriodArray。然后从班级列表中取出每类Clas-sArray。然后再从时间列表中取出一段时间，在这里的整个过程是：先尝试在检查最后产生回溯。对于某个类第n个课时：开始从SubjectArray主体中取出插入，选择科目授课教师进行核查，如果检查成功，位列n+1类，如果不通过，换下一个科目取代……；若所有科目变化完仍然无法通过验证，则有是一个错误的，回到第n-1节课，进行课程的重新选择和排列。重复上面的过程。
排课能否成功所排课程在时间上是否合理的关键在于编排课程的先后顺序，这就决定了优先级在排课过程中所占的地位。优先级的确定直接关系到排课的结果，所以对优先级的设置原则做了如下规定：
（1） 根据课程的安排，必修课的优先级别设置要高于选修课，公共课的优先级别设置要高于必修课；
（2） 学校里不同的课程对学生的认知要求不同，课时数也不同，总课时多的课程的优先级别高于总课时数少的课程：
（3） 学校里，并不是所有课程都要求学生学习，有的课程学生可以选择是否选修该门课程，那么就出现了不同课程上课人数不同，上课人数多的课程的优先级别高于上课人数少的课程；
（4） 一个班级在一个学期要求安排若干门课程，但是由于课程的难易程度不同，学校的要求也就不同，所以不同的课程在一学期内的课时数也是不同的，那么一周课时数多的课程的优先级就要高于一周内课时数少的课程；这样才能符合排课的原理，排出的课程才能合理；
（5） 在学校里，有的课程可能不是在任何时间都可以上课的，那么对时间有特殊要求的课程的优先级别高于对时间没有特殊要求的课程；
（6） 在学校里，有的课程可能对场地有特殊的要求，例如试验实训课要求在实验室会实训室上课，那么在授课场地上有特殊要求的课程的优先级高于对场地没有要求的课程；
（7） 有的课程可能还对教师有特殊的要求，那么对教师有特殊要求的课程的优先级高于对教师没有要求的课程的优先级别。