构建具有大量变量的排班问题

Question

我有一个经典的排课问题，涉及的变量有课程（大约100门）、教室（20个）、学期（8个）和工作日（5天）。

为了简化问题，以下是一些减少后的约束条件。

一天有9个小时。

有些课程是学生必须上的，学期1、3、5、7的必修课（以及2、4、6、8的必修课）不能在同一时间重叠。

课程的时长不同，有的需要2个小时，有的需要3个小时。

有些课程需要在特定的教室上。

同一时间不能有两节课在同一个教室进行。

我正在使用logilabs的Python约束模块。我知道明智地选择变量和领域会让解决问题的时间更短。但我以前从没做过约束编程，现在在构建问题时有点迷茫，不知道从哪里开始。例如：

我可以设定一个约束，比如“同一天同一个教室不能有两节课重叠”。或者先设定“同一天一个教室最多只能预定9个小时”，然后继续缩小解决方案的范围。我估计（虽然没尝试过）第一个约束会比第二个约束花费更多的时间来解决。但这也可能需要（我猜）改变变量和解决方案的领域，或者重建一个更小的问题。我在变量、领域、区间、实现等方面已经有点迷失了。

总之，我需要一些建议，帮助我构建问题、解决方案领域、明智地选择变量等等。

谢谢

更新

使用logilab-constraint包，我做了一个基本的应用程序，并上传到了github上。

Answer 1

我找到了一种解决方案，结合了“明智地选择变量”和“在选择时减少范围”。下面是我在基于Django的排课应用中用到的一些代码片段：

class Course(models.Model):
    name = models.CharField(max_length=255, null=False, blank=False)
    duration = models.PositiveSmallIntegerField(blank=False)
    type = models.ForeignKey(CourseType, blank=False, null=False)
    mandatory = models.BooleanField(default=False)
    '''
        following are the basic constraints  
    '''
    days = models.ManyToManyField(Day, blank=True, null=True)
    terms = models.ManyToManyField(Term)
    rooms = models.ManyToManyField('ClassRoom', blank=True, null=True)


    def __unicode__(self):
        return u'%s' % self.name   

我把基本的约束条件嵌入到类里面，比如“这门课可以在星期一或星期二上，学期可以是1、2或3，教室可以是1、2、3、4或5”，这样我就能在从数据库中选择课程时，直接应用这些基本的约束条件。

一些通用的约束条件，比如“同一天同一时间不能有两门课在同一个教室上”，则是应用在从数据库中选择后减少的变量范围上。

目前看来，这个方法是有效的。

Answer 2

看看这个课程安排示例代码，这是Drools Planner的一部分。其实它们的意思差不多，只是用词稍微不同：每门课程（也就是班级）有很多讲座需要安排到一个教室（就是房间）和一个时间段（每个工作日的每个学期就是一个时间段）。

关键在于保持一个清晰的领域模型，并把它和你的约束规则分开。因为你的课程在小时数上有不同的权重，我建议每个Lecture（讲座）只分配一个startingPeriod（开始时间段），这样如果要把讲座移动到另一个时间段，代码就不会太复杂（只需要重新指定第一个时间段就行）。