自动排课模型算法分析与研究|排课的算法

自动排课模型算法分析与研究

摘 要：
自动排课；
回溯；
研究 一、自动排课需求分析 自动排课问题实质上是时间、教师、班级、教室、课程 这五维关系的冲突问题。采用计算机编排课表，一个基础的 要求就是避免班级、教师以及教室之间的冲突，也就是同时 开课的两个班不能使用相同的教室、不能由相同的教师任教 （在需求分析中，已对排课的要求作了详细描述）。所以首 先解决时间冲突问题是排课算法的重点，再者死锁也是排课 过程中经常出现的问题。所谓死锁，就是指在有效输入的前 提下，课程无法找到满足条件的可排课时间和教室，所以在 排课算法的设计当中，解除死锁也是排课算法要解决的关键。

在时间、教师、班级、教室、课程这五维关系中, 时间、 教师、班级三者之间存在着紧密关系。相对而言, 教室与它 们关系就不那么密切。

由于是设计排课模型，各个学校的具体排课要求不同， 一些不主要的约束条件已忽略。为简化问题约束条件归纳如 下：
1)在同一时间内一个班级仅能由某一教师上一门课；
2)在同一时间内一个老师只可以给一个班级讲一门课 程（不考虑合班上课）；

3)在同一时间内一间教室不能安排两门课程；

4)一个班级的某一门课程只能由一位教师教授；

5)同一时间安排的课程总数不能大于所能提供的教室 总数；

6)某一课程参加学习的总人数不应大于所安排教室的 座位数；

7)所提供教室的属性与课程所需教室的属性一致；

8)同一个班级的同一课程应选择同一间固定的教室。

二、回溯算法 回溯算法是一个既带有系统性又带有跳跃性的的搜索 算法。它在包含问题的所有解的解空间树中，按照深度优先 的策略，从根结点出发搜索解空间树。算法搜索至解空间树 的任一结点时，总是先判断该结点是否肯定不包含问题的解。

如果肯定不包含，则跳过对以该结点为根的子树的系统搜索， 逐层向其祖先结点回溯。否则，进入该子树，继续按深度优 先的策略进行搜索。回溯法在用来求问题的所有解时，要回 溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯 法在用来求问题的任一解时，只要搜索到问题的一个解就可 以结束。这种以深度优先的方式系统地搜索问题的解的算法 称为回溯法，它适用于解一些组合数较大的问题. 三、自动排课算法分析1.排课算法解决时间冲突的方法 在解决时间冲突问题上，通过建立时间表的方法来实现 的。在数据库设计时，建立三个表，分别是：教师时间表、 教室时间表、班级时间表。它们都是为教师、教室、班级这 三者在时间上不发生冲突服务的。教师时间表主要存储每个 教师每个时间段的占用情况；
教室时间表主要存储每个教室 每个时间段的占用情况；
班级时间表主要存储每个班级每个 时间段的占用情况。由于一门课程都是两节课连续上的，那 就可以把两节课看作一个时间段。一天可以上8节课，一个 星期有5天上课，那么一个星期就有20 个时间段。

算法中用1和0来区别某一时间段是否被占用，1表示该 时间段没有被占用，即为空闲状态；
0表示该时间段已被占 用。在排课过程当中，就可以事先通过访问数据库中的时间 表，来判断某一教师、某一教室、某一班级在某一时间段是 否空闲，如果空闲则表示这一时间段可以被占用，否则这一 时间段不能再利用，如果再利用这一时间段，就发生了时间 的冲突，这是排课当中不允许的！ 2.解决死锁的方法 在排课过程当中，如果某班级的某课程永远也找不到合 适的老师或班级，即在班级空闲的时间段里，教师或教室所 对应的时间段没有空闲的，那么这门课程就不可排，接下来 的所有课程都排不了了，这就出现了死锁现象。

因为排课过程是：一门课程编排好后，接着是下一门课程的编排，是一门接着一门编排下去，直到所有的课程编排 结束为止。可见一门课程编排好后，将影响接下来所有没有 编排的课程。所以死锁产生的原因是：当编排某一门课程时， 受到了前面其他几门相关课程的约束制约。

于是当遇到某一门课程不能编排时，即发生死锁，可以 通过返回到上一门课程，重新编排上一门来解决死锁。如果 还不能解决死锁，则再返回再上一门课程，重新编排，直到 解决死锁为止。

如果各种情况都不能解决死锁，这是资源不够用，通过 增加教师，教室资源才能解决死锁问题。

3.运用递归算法和回溯算法相结合 递归算法主要用于把大规模问题分解化成小规模问题 解决，而各个小规模问题的解法都相同。当每个小规模问题 都解决了，那么整个问题都解决了。

可把整个排课问题分解成每个班的排课问题，而每个班 的排课问题又可分解成该班所要上的每门课程的编排问题。

这样问题解决的思路就明朗了。运用递归算法使排课算法大 大简化。通过递归回溯相结合的方法使问题的规模减小，算 法效率提高，是排课算法的核心。

四、结束语 本算法思想通过回溯等方法解决了死锁问题，提供了一 种自动排课模型的思路，为实现自动排课系统打下了基础。

参考文献：[1] 冯思玲,李艳梅,梁瑜. 基于分治和贪心相结合的排 课算法研究[J]现代计算机(专业版), 2009, (03) . [2]曾光清. 贪婪算法在高校排课系统中的运用[J]福建 金融管理干部学院学报, 2007, (06) . [3] 王帮海,李振坤. 基于贪婪算法的自动排课表系统 的研究与实现[J]计算机工程与设计, 2008, (18) . [4]胡小兵,鲁宏伟. 基于模糊专家系统的排课系统关键 技术的研究[J]长沙电力学院学报(自然科学版), 2001, (04)