用约束模型求解研究生排课问题

摘要：根据排课问题的特点，建立约束模型，提出了约束满足、安排等模型概念。采用迭代搜索算法解决排课问题，根据课程、教室、时间、教师、学生等排课中需要考虑的因素进行约束化，再根据约束模型进行搜索安排，得出符合研究生要求的课程安排。实验结果表明，用约束模型解决排课问题是可行的。

关键词：排课；约束化；约束满足；迭代搜索

中图分类号：TP391 文献标识码：A 文章编号：1007-9599 (2011) 23-0000-02

The Constraint Model for Postgraduate Course Scheduling Problem

Liu Rencheng

(School of Information Science&TechnologyBeijing Forestry University,Beijing 100083,China)

Abstract:According to the features of timetabling problem,built up a constraints model,providing definitions such as constraint satisfaction problem and assignment.Use iterative search algorithm to solve timetabling problem,basing on constraints of courses,room,time,

teachers and students,then according to constraints model to search assignments,find a feasible solution.The results show that constraints model is suitable for timetabling problem.

Keywords:Course scheduling;Constraint;Constraint satisfaction;

Iterative search

一、引言

1975年，美国S.Even等人证明了课程表问题是NP（Non-deterministic Polynomial）完全问题，即多项式复杂程度的非确定性问题，也就是找不到多项式时间求解算法，并且宣布了这一时空组合问题的学术地位和难度。从此各种针对排课问题的算法应运而生，其中最知名的算法包括：遗传算法、禁忌搜索算法、模拟退火法、粒子群算法等，却很少有专门针对研究生的排课算法，在遗传算法、禁忌搜索算法和模拟退火法中，往往是把班级作为一个要素进行排课，从而忽略了学生的兴趣选择。本文旨在研究研究生排课，并针对研究生排课普遍存在时间多、课程少、研究主动性强等特点，着重研究以学生为基本要素，以学生需求为主要内容的排课算法，使研究生排课在实际应用中能充分发挥学生的自主性和主动性。

二、排课问题的描述

为了把排课中遇到的所有因素量化，本研究建立了约束模型。排课中的客观因素包括时间、教室和课程。主观因素则有教师和学生的要求。无论是客观因素还是主观因素都会转化为约束。约束模型分为两种类型：硬约束和软约束。

（一）硬约束

硬约束是指不可违反的条件，硬约束有两个约束等级：必须的和禁止的。硬约束包括：

1.一个教室在同一时间只能安排一门课程。

2.一个教师在同一时间只能教一门课程。

3.教室容量不能大于在该教室上课的学生数量。

4.一个学生在同一时间只能学习一门课程。

5.一个教师的连续两门课程的上课教室距离不能超过75m（假设课间时间是15min）。

6.每门课程都有固定的教学资源，包括教室和上课时间。

（二）软约束

软约束是指在满足以上硬约束的基本条件的基础上，提出更多要求的约束条件。软约束包含5个等级：比较优先的、优先的、一般的、不优先的、比较不优先的。软约束包括：

1.每个学生的课程均匀分布在一周的周一至周五。

2.每个学生的连续两门课程的上课教室距离不超过100m（假设课间时间是15min）。

3.每个教师的课程尽量均匀安排在一周的周一至周五。

4.尽可能地满足教师对于时间和教室的特殊要求。

（三）排课问题的数学模型

模型化

定义：排课问题可以描述为一个满足约束问题的模型，它是一个三维的关系=(V，D，C)，并且满足如下条件：

1.V={v1，v2，……，vn}是一个有限的变量集合。

2.D={Dv1，Dv2，……，Dvn}是一个域的集合。

3.C={c1，c2，……，cm}是一个有限的约束集合。

变量v是指一个课程A在哪个教室由哪个教师在什么时间上课，而值的集合Dv是指对于这个变量可能选择的，比如说课程A可以在教室302由王老师在周四上午8点至10点上课，也可以在教室402由李老师在周三下午3点至5点上课。这两种可能性组成了集合Dv。约束c是对变量取值限制，比如说有这么一条约束：王老师只能在周三上课，那么对于上面的两个值就只能取后者。

三、迭代搜索算法

迭代搜索使用迭代计算搜索，如下图1。在第一步，设定=(V，D，C)是一个约束满足问题，α是一个初始化安排，σ是当前安排，β是最好的安排。每次迭代中都要根据当前安排σ判断是否可以继续，当继续时一个变量A是最初被选中。一旦一个变量A被选中，一个值a从它的域DA被安排选中。但是，即使是最佳值被选中，它的安排，所选择的变量也可能会造成很多已经安排的变量的硬冲突。这些冲突安排会被从解决方法中移除，重新变为未安排。最后，选中的值安排给选中的变量。

图1 迭代搜索算法图

算法尝试从一个可行的解决方法移动到另一个通过重复安排一个选中的值a到一个选中的变量。在这个搜索中，所有硬约束的可行性在每次迭代中被没有指定变量的冲突安排通过函数conflicts检查。当要求的解决方法被找到时，或者可变的时间到达时，搜索结束，例如，当迭代的最大次数或者可变时间到达。最好的解决方法返回。

定义1：安排，对于变量v选择了在教室402由李老师在周三下午3点至5点上课，我们称之为一个安排。每一个安排存在如下关系：

存在∀v/a，w/b∈η，而且时，。

一个η的元素v/a表示变量v被值a所安排，因此我们得出，当时，一个安排产生了，也就是说所有的变量都被满足。

我们所要寻找的解决方法就是约束满足问题是变量集合V的完整的安排σ，这个安排能够满足所有的约束。

而所谓的约束满足可以被定义为如下：一个变量a1，a2….an的约束c被安排满足，如果安排包含所有的变量a1，a2….an并且约束被安排满足，那么如果安排可以扩展为安排，并且安排包含所有的变量a1，a2….an，那么约束c被安排满足定义公式如下：

定义2：设定=(V，D，C)是一个约束满足问题，限定安排对于一个约束cC是σc={v/a|v/aσ&vV}

V是由约束c定义的一个变量的集合。

定义3：设定=(V，D，C)是一个约束满足问题，安排σ假定能够满足约束cC就必须要满足以下条件：

|c|=|V|且c(c)总是为真

或者当|c|=|V|且c(c)

在搜索中，在每次迭代步骤之后，我们有一个所有变量的子集的安排。这个安排要满足每个硬约束，我们称这个安排是可行的安排。

定义：设定=(V，D，C)是一个约束满足问题，如果说可行的安排能够满足所有的约束cC，那么必须满足以下条件：

|c|=|V|且c(c)总是为真

或者当|c|=|V|且c(c)

因此在每次迭代步骤后有一个安排，必须坚持一致性技术，是为了强迫满足上述定义的所有硬约束。同样的，安排的一致性关于任何随意的一致性技术ζ可以在搜索中执行。这意味着，执行每次迭代步骤后，我们有一个安排，符合一致性检查ζ()，ζ是一致性技术而且是解决约束满足问题。

函数conflicts的任务是执行这样的一致性。它返回一个当前安排的子集η，如此新的安排(-η){A/a}是一贯的关于已经使用的一致性技术ζ，A是变量，a是当前迭代步骤选择的值）。

定义5：设定=(V，D，C)是一个约束满足问题，是的一个一致性（一部分）安排，AV是一个选中变量，aDA是一个选中值。函数conflicts返回η使得安排(-η){A/a}是的一个一致性（部分）安排，代表给定的一致性技术ζ。

在上面定义中，我们假设在变量A的域DA，只是那些值，这些值是和所有的关于一致性技术ζ的约束保持一致。这意味着每一个值aDA，一致性检测ζ({A/a})为真。至于基于满足约束的一致性，意思是每个来自域DA的值a，所有的约束都满足安排{A/a}.否则，如果选中一个不保持一致的值a，由此产生的安排不会一致，因为它包含安排{A/a}，是不一致的。这些不连贯的值会永久的从域中过滤掉，在没有损失的搜索开始时（例如，问题用一个空安排要求一致性技术），因为没有一个（部分）约束安排包含这种值。

同样有一个对应在这些“冲突”变量的集合和在回溯基本算法中的不好集合之间。一个不好集合是那些不能满足（比如，没有可行的解决方法包含这个集合）的当前（部分）安排的子集。潜在的，一个变量，不同于A，来自于每个不好集合，可以从安排{A/a}中计算，需要被选进我们的冲突集合。

四、实验与分析

本文使用迭代算法进行排课，资源如下：教师两名：张三和李四；教室一间；课程两门：大学英语（5个教学班，每个教学班每周两学时），大学英语听说（7个教学班，每个教学班每周四学时）。排课结果如下：

图2 教室排课结果表 图3 张三教师上课时间表

图4 李四教师上课时间表

有以上三张时间表可知，教室的时间可以有效的利用，同时两位教师的时间可以合理的安排，不会产生时间冲突。

五、结论

本文对排课问题做了大致介绍，并且对通过迭代算法，使用约束模型进行了说明，最后是对该算法在排课问题中的应用进行分析。在实践中，针对多种情况的检验，所使用的方法可以合理的分配课程时间表，满足大部分教师和学生的需求，证明了约束模型在排课问题中运用的合理性。

结果表明，用约束模型解决排课问题是可行的，能够尽最大可能的满足学校的排课需求。

参考文献

[1]王仲华,卢娇丽.遗传算法优化求解排课问题的应用研究[J].科学之友,2008,17,3:234-23

[2]陈守家,付霞,周欣.基于遗传禁忌算法结合解决排课问题[J].计算机应用,2007,27(7):1806-1808

[3]王伟,余利华.基于贪心法和禁忌搜索的实用高校排课系统[J].计算机应用,2007,11(4):1001-1005

[4]徐潘萍.浅谈模拟退火算法在自动排课系统中的应用[J].井冈山学院学报（自然科学）,2008,6(3):1673-4718

[5]吴瑕,蒋玉明.利用免疫粒子群算法解决排课问题[J].计算机工程与设计,2010,31(17):3872-3875