这是我很长一段时间以来一直在思考的问题。作为老师和程序员的儿子，这很早就发生在我身上……但是我仍然没有找到解决方案。

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

健全性检查

• 老师不能同时教两个课
• 学生不能同时上两节课
• 一些老师一周必须至少休息一天
• 时间表应涵盖一周中的所有日子
• 主题X每周必须有一定的确切时间
• …

优先

• 每位教师的日程安排应尽可能紧凑（即，教师应连续一天全天工作，并尽可能不停顿）
• 放假的老师应该能够在哪一天表达自己的偏好
• 兼职工作的老师应该能够偏向于在工作日的开始还是结束时工作。
• …

现在，经过几年没有找到解决方案（同时又学习了一两件事……）之后，我意识到这听起来像是一个NP难题。

它被证明是NP硬性的吗？

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

看着这个问题让我思考了这个问题，以及在这种情况下遗传算法是否适用。但是，在保持健全性检查规则的同时，很难改变可能性。我也不清楚如何区分不兼容的需求。

一个小的附录，可以更好地说明问题。这适用于意大利学校风格的教室，在该教室中，所有学生都属于不同的班级（例如：A年级第一节），并且老师在班级之间移动。同一班级的所有学生都有相同的时间表，没有选择参加哪些课程的选择。