建立具有大量变量的时间表问题

Question

我有一个经典的时间表问题，由变量类（~100）、房间（20）、学期（8）和工作日（5）组成。

为了简化问题，以下是减少的约束。

一天是9个小时。

有些课程是学生的必修课，第 1、3、5、7 学期（以及 2、4、6、8）的必修课不得相互重叠。

课程的时长不同，有的为 2 小时，有的为 3 小时。

有些课程应在特定房间进行。

同一堂课不能同时进行两场讲座。

我将使用 logilabs python 约束模块。我知道明智地选择变量和域将减少解决问题的时间。问题是我以前从未做过约束编程，并且很难构建问题以找出从哪里开始以及从什么开始。例如：

我可以设置一个约束，例如“同一天、同一房间的两个班级不能重叠彼此的时间段”。或者从“同一天预订房间的时间不得超过 9 小时”开始，然后继续缩小解决方案域。我估计（没有尝试）第一个约束将比另一个约束花费更长的时间来解决。但它还需要（我猜）更改变量和解决方案域或重建较小的问题。我已经对变量、域、间隔、实现等有点迷失了。

长话短说，我需要一些指导来构建问题、解决方案域、明智地选择变量等。

谢谢

更新

使用 logilab -constraint 包我已经制作了一个基本应用程序并将其上传到 github

Answer 1

看看 curriculum课程示例代码的Drools 规划器。基本上是同一件事，但术语略有不同：每门课程（=班级）都有许多讲座，需要安排在一个房间（=房间）和时段（=每个工作日的每个学期都是一个时段）。

诀窍是保持一个干净的域模型并将其与约束规则分开。
由于您的课程在小时数方面具有不同的权重，因此我建议仅为 Lecture 分配一个 startingPeriod，因此将 Lecture 移动到另一组的代码并不需要太多。期间（只需重新分配第一个期间）。

Answer 2

我最终得到了一个将“明智地选择变量”和“减少选择域”捆绑在一起的解决方案。以下是我正在做的基于 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"，这允许我直接应用这些
选课之初的基本限制
数据库。

诸如“同一天的相同时间之间不能在同一房间内开设两门课程”之类的一般约束适用于来自数据库中完成的选择的减少的变量域。

看来现在还在工作。