algorithm - 教师时间表算法

Question

这个问题困扰我很久了。作为一名教师和一名程序员的儿子，我很早就想到了......但我仍然没有找到解决方案。

这就是问题所在。需要使用一些约束为学校创建时间表。这些通常分为两类:

完整性检查

• 一个老师不能同时教两个类
• 一个学生不能同时上两个类
• 部分教师每周必须至少休息一天
• 时间表应涵盖一周中的所有日子
• 受试者 X 每周必须有准确的某某时间
• ...

首选项

• 每位教师的日程安排应尽可能紧凑(即，教师应连续工作一整天，尽可能不间断)
• 有休息日的教师应该能够表达对哪一天的偏好
• 从事兼职工作的教师应该能够表达偏好是在上课时间还是在放学时间工作。
• ...

现在，在几年没有找到解决方案(并同时学习一两件事......)之后，我意识到这听起来像是一个 NP-hard 问题。

它是否被证明为 NP-hard？

有没有人知道如何破解这个东西？

查看this这个问题让我想到了这个问题，以及遗传算法在这种情况下是否可用。然而，在保持完整性检查规则的同时改变可能性是非常困难的。我也不清楚如何区分不兼容的要求。

---

一个小的附录，可以更好地说明问题。这适用于意大利学校风格的教室，其中所有学生都在不同的类(class)(例如:第一年 A 部分)并且教师在类(class)之间移动。同一类(class)的所有学生都有相同的时间表，并且没有选择上哪节课的权利。

Answer 1

我是学生信息系统调度程序部分的开发人员之一。在我们最初处理调度问题的过程中，我们研究了遗传算法来解决约束满足问题，尽管我们最初是成功的，但我们意识到这个问题有一个不太复杂的解决方案(参加学校调度研讨会后)

我们目前的实现效果很好，并使用暴力和智能启发式方法在短时间内获得有效的时间表。首先建立主时间表(将类(class)分配给教师)，考虑到每位教师的所有限制，同时最大限度地减少学生冲突的可能性(基于他们的类(class)要求)。然后使用相同的方法安排学生上课。

这样做可以让您先让机器构建一个主计划，然后在需要时让人工对其进行调整。

调度程序当前的实现是用 perl 编写的，但我们早期访问的其他选项是 Prolog 和 CLIPS(专家系统)