教师时间表算法

这是我长期以来一直存在的问题.作为一名教师和程序员的儿子,我很早就想到了......但我仍然没有找到解决方案.

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

理智检查

老师不能同时教两门课

学生不能同时学习两节课

一些教师必须在一周内至少休息一天

时间表应涵盖一周中的所有日期

受试者X每周必须完全正常

...

喜好

每位教师的日程安排应尽可能紧凑(即教师应该连续一天工作,如果可能的话,没有暂停)

休息日的教师应该能够在哪一天表达偏好

从事兼职工作的教师应该能够表达是否在学校开始或结束时工作的偏好.

...

现在,经过几年没有找到解决方案(同时学习一两件事),我意识到这就像一个NP难的问题.

它被证明是NP难吗？

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

看看这个问题让我想到了这个问题,以及在这种情况下遗传算法是否可用.然而,在保持理智检查规则的同时,很难改变可能性.我还不清楚如何区分不兼容的要求.

一个小的附录,以更好地说明问题.这适用于意大利学校风格的教室,所有学生都在不同的班级(例如:第1年A部分),教师在不同课程之间移动.同一班级的所有学生都有相同的时间表,并且无法选择参加哪些课程.

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

我们当前的实施工作很有效,并使用强力启发技术在短时间内获得有效的时间表.首先建立主要时间表(向教师分配课程),同时考虑到每个教师所具有的所有约束,同时最小化学生冲突的可能性(基于他们的课程要求).然后使用相同的方法在课程中安排学生.

这样做可以让您首先建立一个主计划,然后根据需要进行人工调整.

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