基于智能排课算法的设计与实现

摘　要：本文根据回溯，递归等算法思想，解决了排课过程中死锁的问题。 通过具体分析，实现了该算法，为排课系统智能化打下了基础。

关键词：智能排课；回溯；实现
根据论文《自动排课模型算法分析与研究》给出了智能排课模型算法思想。根据这一思想，算法可实现如下：
　　一.时间表的初始化：
　　排课算法要用到每个教师、每个教室、每个班级的时间信息。所以首先要对数据库中的教师时间表，教室时间表，班级时间表进行初始化。1表示空闲，0表示被占用。
　　二.排课算法的粗流程：
　　本算法时以班级为单位来进行排课的，即：从“班级”表中读出班级信息，从中随机选出一个没有排课的班级，然后给它排完它所有要上的课程。直到所有班级的课程都编排排完成，这样整个的排课任务就完成了。
     所以粗流程分为两个部分：1.给所有班级进行排课。2.给某一班级进行该班级所有要授课程的编排。其中，1流程是包括2流程的。
　　1、给所有班级进行排课粗流程：
1）统计所有要排课班级的总数，把班级总数存放入变量n。在用一个变量i存放n的值.
　　2)判断i是否为0，如果是则程序结束，否则继续下面的流程。
　　3）随机选取一个尚未编排课程的班级。
　　4）把选中的班级的所有课程都编排完成。
　　5）i减1。
　　6）转至 2）。
     2、给某一班级排完它所有的课程的粗流程：
1）统计一下这个班级要上多少门课程，把课程总数存放入变量m。在用一个变量i存放m的值。
　　2)判断i是否为0，如果是则程序结束，否则继续下面的流程。
　　3）随机选取一门尚未编排的课程。
　　4）为此课程安排一位符合条件的教师。
　　5）为此课程安排一间符合条件的教室。
　　6）把班级、课程、教师、教室这一组记录插入核心总课表。
　　7）i减1。
　　6）转至 2）。
　　三. 排课算法的实现：
通过排课粗流程的分析,已经知道了排课算法的一个大致的思想,下面详细的分析排课算法。
　　1) 统计所有要排课班级的总数:
　　根据数据库中表：班级，统计表的行数就可得班级的总数。
　　2)判断一个班级是否已编排课程
根据班级数目，建立一个数组，来标识每一个班级是否已编排课程，1表示没有编
课程的班级，0表示已编排课程的班级。
　　3)当一个班级的所有课程都编排结束后，就要进入下一个班级课程的编排，这时就用到递归的方法．即在每排一个班级的所有课程时，就用调用一次递归。由于可能出现某一班级的某一课程不能编排成功的死锁现象，这时就要用到回溯的方法进行解决，本算法中就是调整班级排课的顺序。算法中在每次递归调用中又建立了一个数组来记录所有班级顺序的排列组合。在资源满足的条件下，总有一种顺序是可以编排完所有的班级课程的。对于给某一班级排完它所有的课程，也是同样的道理。
　　4）统计某一班级要上的课程的总数:
根据数据库中表：课程，查询该班级的课程，从而统计出该班级要上的课程的总数。
　　5)判断某班级的某课程是否已编排
　　根据某一班级要上的课程的总数，建立一个数组，来标识每一个课程是否已编排，1表示该课程没有编排，0表示该课程已编排。
　　６）为课程安排一位符合要求条件的教师，安排一间符合要求条件的教室
　　先为某一班级的某一课程随意选取选一位教师和一间教室，之后在数据库中的教师时间表，教室时间表，班级时间表中读出该班级、教师、教室的时间信息。通过把这三者的时间表相乘，把结果存放在一个数组中，值为“1“的元数就是它们的共同空闲时间段。
　　如果共同空闲时间段的数目大于或等于此课程的周课时的一半，那么此教师、教室就符合要求。否则不符合要求，那么就要换一个教师或教室，直到某个教师或教室和此时要排的班级的此课程共同空闲时间段的数目满足要求为止。如果还没有符合要求的，就要通过回溯来解决这个问题了。
　　７）生成一条核心课表记录
　　当为某一班级的某一课程安排好一位符合要求的教师和一间符合要求的教室，再选一它们共同空闲时间段后，一条核心课表记录就可以生成了。
　　生成一条核心课表记录之后，此班级和对应为它要上的某一课程选好的相应教师、教室的某一共同空闲时间段就要被占用，所以在生成一条核心课表记录之后，要把此班级和对应为它要上的某一课程选好的相应教师、教室，它们的数据库中时间表中选中的同空闲时间段置0，表示它们这个时间段已被占用。为下面的课程的编排，在时间上不发生冲突打下了基础。
　　８）回溯算法的实现
　　由于用到回溯算法，在每生成一条核心课表记录之前，都要保存好此时的时间信息状态，即都要用时间变量保存此时待排课的班级的时间表，为此班级的某课程选好的符合要求的教师、教室的时间表，为回溯做准备。
　　如果递归遍排下一门课程时。下一门课程找不到符合要求的教师或教室时。就要返回到上一层递归。通过回溯来解决这一问题。因为回溯要回到分支的根状态，所以要还原分支的根状态，即把时间变量保存的信息还原到各个时间表，把本次产生的核心课表记录删除，同时把此课程置为没有编排过状态。这样就还原到产生本核心课表记录的初始状态，那么就可以换另一条路再试了，直到所有课程都编排成功，此时回溯算法的思想也得以实现了。
四.排课算法的详细流程
　　1) 统计所有要排课班级的总数，建立班级数组，用于标识某班级是否已编排过课程。初始化班级数组，即数组元数都为1 ，表示初始时，每个班级都未编排过课程。
　　2）和建立辅助班级数组，把班级数组的值存入辅助班级数组，用来记录所有班级排课顺序的排列组合。提供了回溯的解空间。
　　3)判断尚未编排课程的班级是否为0，如果是转至18），否则继续下面的流程。
　　4）随机选取一个尚未编排课程的班级，相应的班级数组的标识位置0，表示此班级已编排课程。相应的辅助班级数组的标识位也置0。
　　5）统计一下这个班级要上多少门课程，建立课程数组，用于标识某课程是否已编排过。初始化课程数组，即数组元数都为1 ，表示初始时，每个课程都未编排过。
　　6）和建立辅助课程数组，把课程数组的值存入辅助课程数组，用来记录该班级所有要上课程编排顺序的排列组合。提供了回溯的解空间。
　　7）判断此班级尚未编排课程是否为0，如果是递归下一个班级的编排，即转至3），否则继续下面的流程。
　　8）随机选取一门尚未编排的课程，相应的课程数组的标识位置0 ，表示此课程已被编排过。相应的辅助课程数组的标识位也置0。
　　9）为可教授此课程的教师建立教师数组，用于标识某教师是否已选中过。初始化教师数组，即数组元数都为1 ，表示初始时，每个教师都未选中过。
   10）判断可教授此课程的教师是否都被选中过。如果是递归返回，把时间变量保存的信息还原到各个时间表，把本次产生的核心课表记录删除，把相应的课程数组的标识位置1，这样就还原到产生本核心课表记录的初始状态。否则选取一名可教授此课程并且没有被选中过的教师。把相应的教师数组的标识位置0，表示此教师已被选中过。
　　11）为满足此课程的教室（即满足此课程的教室类型，满足此班级的总人数）建立教室数组，用于标识某教室是否已选中过。初始化教室数组，即数组元数都为1 ，表示初始时，每个教室都未选中过。
　　12）判断满足此课程的教室是否都被选中过，如果是转至10），选取一间没有被选中过的教室，并且把相应的教室数组的标识位置0，表示此教室已被选中过。
   13）判断班级、教室、教师的共同空闲时间段的数目是否大于或等于此课程的周课时的一半。如果是继续下面的流程。否则转至12），
　　14）保存好此时的时间信息状态，即都要用时间变量保存此时待排课的班级的时间表，为此班级的某课程选好的符合要求的教师、教室的时间表，为回溯做准备。
　　15）随机选取它们数目为周课时一半的共同空闲时间段，就可把班级名、所授课程、授课教师、上课地点，上课时间这一组记录插入核心总课表。
　　16）把此班级和对应为它要上的某一课程选好的相应教师、教室，它们的数据库中时间表中选中的同空闲时间段置0，表示它们这个时间段已被占用。
　　17）递归下一门课程的编排，即转至7）。
　　18）结束。
　　参考文献：
[1]毕波，自动排课模型算法分析与研究，佳木斯教育学院学报，2012，（2）
[2] 冯思玲,李艳梅,梁瑜。基于分治和贪心相结合的排课算法研究，现代计算机(专业版), 2009, (03)。
[3] 宗薇， 高校智能排课系统算法的研究与实现，计算机仿真 ,2011， (12) 。 本文链接：http://www.qk112.com/lwfw/jiaoyulunwen/gaodengjiaoyu/61730.html