logo标签列表

创建学校课程表的算法

algorithmlanguage-agnosticnp
108

我一直在想是否有已知的算法来创建学校课程表。基本上，它是关于优化给定班级-科目-教师关联下的“时间分散”（教师和班级均适用）。我们可以假设在输入时，我们有班级、课程主题和与之相关联的教师集合，并且课程表应该在早上8点到下午4点之间。

我猜可能没有精确的算法，但也许有人知道一个良好的近似值或开发它的提示。

2
感谢所有的回答。看起来这个算法需要更多的研究。我会考虑将其作为硕士论文或小型商业应用的好课题。如果我写了一个，我会在这里告诉你们的 ;) - cand
11
正如StackOverflow的Ian Ringrose对另一个问题所说的：“在编写调度软件方面，仍然有很多博士学位等待获得。” - Reed Debaets
18个回答
107
这个问题是NP-Complete的！
简单来说，需要探索所有可能的组合，以找到可接受解决方案的列表。由于该问题出现在各种学校的情况存在变化（例如：是否有关于教室的限制？某些班级有时分为子群吗？这是每周的时间表吗？等等），因此没有一个已知的问题类与所有调度问题相对应。也许，背包问题与大型这些问题有许多相似之处。
确认这是一个难题，并且人们经常寻求解决方案的证明，是检查这个（长）（大部分为商业）软件调度工具列表 由于涉及的变量数量很大，其中最大的来源通常是教师的愿望；-)，因此通常不实际考虑枚举所有可能的组合。相反，我们需要选择一种方法来访问问题/解决方案空间的子集。
- 在另一个答案中引用的遗传算法（或者，依我之见，似乎）非常适合执行这种半引导搜索（问题是为候选人找到一个好的评估函数，以便保留到下一代）
- 图重写方法也在这种类型的组合优化问题中有用。
与其专注于自动时间表生成程序的特定实现，不如建议一些可以应用的策略，在定义问题的层面上。总的来说，在大多数实际的调度问题中，需要做出一些妥协，不能完全满足所有明确或隐含的限制。因此，我们可以通过以下方法帮助自己：

  • 定义并排列所有已知的约束条件
  • 通过手动添加一组额外的约束条件，减少问题空间。
    这可能看起来有些反直觉，但例如，通过提供一个初始的、部分填充的时间表（大约占据30%的时间段），以满足所有约束条件，并将这个部分时间表视为不可变，我们可以显著减少产生候选解所需的时间/空间。另一种额外约束条件帮助的方式是“人为地”添加一个约束条件，防止在某些星期几教授某些科目（如果这是一个每周的日程安排...）；这种类型的约束条件会减少问题/解决方案空间，而通常不会排除太多好的候选者。
  • 确保问题的一些约束条件可以快速计算出来。这通常与用于表示问题的数据模型的选择有关；其想法是能够快速选择（或剪枝）一些选项。
  • 重新定义问题，并允许一些约束条件被打破几次（通常是在图的末端节点）。这里的想法是要么删除最后几个时间段中的一些约束条件以填补空缺，要么让自动计划生成器程序停止完成整个时间表，而提供给我们一些合理的候选方案列表。人类通常更适合完成难题，并根据不与自动逻辑共享的信息来打破一些约束条件（例如，“下午不上数学”规则有时可以为“高级数学和物理”班级打破；或者“最好违反Jones先生的一个要求而不是Smith女士的一个要求...;-)”）。

在校对本答案时，我意识到它没有提供一个明确的回答，但它仍然充满了实用的建议。希望这能帮助解决这个“难问题”。

3
非常好的、准确和详细的回答，感谢您提供的提示和关于 NP-完全性的提醒（这也是我的猜测）。 - cand
3
你有关于该问题NP完备性的任何引用文献吗？ - Don
我使用了最大流算法来大大减少这个问题。请查看我的答案。 - Kemsikov
59

这是一团糟，一团混乱。除了其他答案已经非常完整，我想指出我的家庭经验。我的母亲是一名教师，曾参与过排课。

结果发现让计算机完成这项任务不仅难以编码本身，而且因为有些条件很难针对预先制作的计算机程序进行规定。例如：

  • 一个老师在你的学校和另一个学院都教授。显然，如果他在那里结束了10:30的课程，他不可能在10:30开始在你的场所上课，因为他需要一些时间来往两个学院之间通勤。
  • 两位教师结婚了。一般来说，在同一班级中不应该安排两位已婚教师。这两位教师必须有两个不同的班级。
  • 两位教师结婚，并且他们的孩子在同一所学校就读。同样，您必须防止这两位教师在其孩子所在的具体班级中教书。
  • 学校有单独的设施，例如一天班级在一个学院，另一天在另一个学院。
  • 学校有共享实验室，但这些实验室仅在某些工作日开放（例如出于安全原因需要额外人员的情况）。
  • 一些教师对空闲日有偏好：有些人喜欢星期一，有些人喜欢星期五，有些人喜欢星期三。有些人喜欢早上早到，有些人喜欢晚点到。
  • 不应该出现这样的情况：比如第一节课是历史课，然后是三个小时的数学课，再加上一个小时的历史课。这对学生和老师都没有意义。
  • 你应该平均分配各种科目。把一周的前几天都排满数学，然后剩下的时间只留给文学是没有意义的。
  • 你应该给一些老师连续两个小时来进行评估测试。

正如您所看到的，这个问题并不是NP完全问题，而是NP疯狂问题。

所以他们做的是，用小塑料嵌块制成一张大表，并将这些嵌块移动到满意的位置上。他们从不从头开始制定计划：通常从去年的时间表开始，进行调整。

12
“NP-insane”- 挺好的名字 ;) 我同意这是一个非常复杂的问题，感谢你对“现实世界”处理此问题的评论。我的父亲和女友也是教师，我知道大多数学校都有带塑料嵌板的桌子 - 这让我想到了可能的算法来解决这个问题 - 因为如果一个人能够解决它，也许就可以将其写成算法。 - cand
10
您想编写的是专家系统：由一系列启发式规则构成的系统。除了专家系统，遗传算法是最佳选择之一。难度不仅在于解决问题，还在于明确问题及其约束条件。 - Stefano Borini
1
你说得对，这个问题需要提供一系列复杂的条件和限制来满足要求，可能是以“可接受”的解决方案评级。我同意使用遗传算法，它们应该很适合这个问题，同时我认为最好先用简单的条件集开始开发，并在获得正确答案后进行优化。 - cand
1
你也可以将这些限制和目标直接转化为MAXSAT。相比遗传算法，MAXSAT算法通常更可靠，但由于像数学课应该在一周内分散安排之类的目标，可能会出现子句爆炸的情况。 - Jules
29

国际排课竞赛2007设有课程调度和考试安排两个项目。许多研究者参与了该竞赛。尝试了许多启发式算法和元启发式算法，但最终局部搜索元启发式算法（如禁忌搜索和模拟退火）明显击败其他算法（如遗传算法）。

看一下部分决赛选手使用的两个开源框架:

18

我的其中一个学期作业是基于遗传算法的班级课表生成。

整个课表就像一个“有机体”。对通用遗传算法方法进行了一些改变和限制：

  • 建立了“非法课表”规则：同一教室的两个班级，一个老师同时教授两个小组等情况。这些突变立即被视为致命并立即产生新的“有机体”代替“死亡”的有机体。初始课表是通过一系列随机尝试来生成合法（但毫无意义）的。致命突变不计入迭代中的变异数量。

  • “交换”变异比“修改”变异更常见。变化仅在有意义的基因部分之间发生 - 不会将教师替换为教室。

  • 指定某些2小时的捆绑、为同一组连续分配相同的通用教室、保持教师工作时间和班级负载连续性分配了一些小奖励。为给定科目分配正确的教室，保持课程时间在范围内（上午或下午）等分配适度奖励。为指定科目的正确数量、为教师分配适当的工作量等指定大奖励。

  • 教师可以创建他们的工作量时间表：“想要在这个时间工作”、“可以在这个时间工作”、“不喜欢在这个时间工作”、“不能在这个时间工作”，并分配适当的权重。全天24小时都是合法工作时间，除了晚上非常不受欢迎。

  • 权重函数...哦，对了。权重函数是选定的特征和属性赋值的巨大、庞大的乘积。它非常陡峭，一个属性就能轻松地使它增加或减少一个数量级——而在一个生物体内有数百或数千个属性。这导致权重的数字非常大，因此需要使用大数库(gmp)进行计算。对于一个小规模测试用例，包括10组、10名教师和10间教室，初始设置以10^-200something为起点，最终以10^+300something为终点。当函数更为平缓时效率完全低下。同时，当学校规模变大时，数值的增长距离也会变得更大。

  • 从计算时间上看，较小的人口(100人)在较长时间内与较大的人口(10k+)在较少的世代内所产生的结果质量基本相同。

  • 在某个1GHz CPU上，计算稳定到10^+300大约需要1小时，生成出来的课程表看起来相当不错，适用于以上述10x10x10的测试用例。

  • 这个问题可以通过提供网络设施来并行化处理，以便在正在运行计算的多台电脑之间交换最佳标本。

    • 最终的程序从未见过日光，只为我赢得了一个良好的学期成绩。它展示了一些潜力，但我从未有足够的动力添加任何GUI，使其对普通公众可用。

    6
    那么打开它并宣传它，尝试吸引一些学者进来？重复使用它用于进一步的项目？从技术上讲，像这样为300名员工编制最佳班表的程序对学校来说是有价值的，并且他们不介意花几天时间来基因计算最佳班表。考虑批处理。哈喽，硬件和软件合同;) - jcolebrand
    1
    太好了！我想知道权重函数是否可以使用0到1范围内的浮点数完成。 - Craig McQueen
    1
    @Craig：这种扁平的东西会导致人口随着时间的推移停滞甚至退化，因为随机突变带来的负面影响比繁殖/选择能够抵消的更多。只有极其陡峭的优质函数才能实现稳定增长。当然，该函数可以被归一化，但是，“稍微好一点”的基因仍然必须具有更高的生存几率。 - SF.
    11

    我的排课算法使用FET (Free Timetabling Software, http://lalescu.ro/liviu/fet/) 实现，是一个成功的应用程序。

    该算法是启发式的。我称其为“递归交换”。

    输入：一组活动 A_1...A_n 和相关约束条件。

    输出：一组时间 TA_1...TA_n（每个活动的时间段。这里为了简单起见不考虑教室）。算法必须将每个活动放在一个时间段内，并遵守约束条件。每个 TA_i 的取值范围为 0 (T_1) 到 max_time_slots-1 (T_m)。

    约束条件：

    C1）基本约束条件：不能同时进行的一组活动的列表（例如，A_1 和 A_2，因为它们有相同的老师或学生）；

    C2）许多其他约束条件（为了简单起见，此处不予考虑）。

    排课算法（我称之为“递归交换”）：

    1. 将活动按照难度排序，先处理最困难的。这不是必要步骤，但可以将算法速度提高10倍或更多。

    2. 按照上述顺序，逐个尝试将每个活动(A_i)放入允许的时间段中。搜索可用于A_i的时间段(T_j)，并在遵守约束条件的情况下将该活动放置在其中。如果有多个可用时间段，请选择一个随机的时间段。如果没有可用时间段，请进行递归交换：

      a. 对于每个时间段T_j，请考虑将A_i放入T_j会发生什么。将会有一系列其他活动与此移动不同意（例如，活动A_k在同一时间段T_j中，并且具有与A_i相同的教师或学生）。为每个时间段T_j保留冲突活动列表。

      b. 选择具有最少冲突活动数量的时间段(T_j)。假设此时间段中的活动列表包含3个活动：A_p，A_q，A_r。

      c. 将A_i放置在T_j，并使A_p，A_q，A_r未分配。

      d. 递归地尝试将A_p，A_q，A_r（如果递归级别不太大，例如14，并且自步骤2开始计算的递归调用总数不太大，例如2*n）放置在A_i上（如步骤2所述）。

      e. 如果成功放置了A_p，A_q，A_r，则返回成功，否则尝试其他时间段（转到步骤2b），选择下一个最佳时间段。

      f. 如果所有（或合理数量的）时间段都没有成功尝试，请返回失败。

      g. 如果我们处于级别0，并且没有成功放置A_i，请像步骤2b和2c中那样放置它，但不进行递归。现在我们还有3-1 = 2个活动要放置。 转到步骤2)（这里使用了一些避免循环的方法）。

    1
    FET对我非常有用。谢谢@Liviu Lalescu！ - Noel Llevares
    10

    这个问题比看上去的要难。

    正如其他人所暗示的，这是一个NP完全问题，但让我们分析一下这意味着什么。

    基本上，这意味着你必须查看所有可能的组合。

    但“查看”并没有告诉你需要做什么。

    生成所有可能的组合很容易。它可能会产生大量数据，但你不应该在理解问题的这部分概念方面遇到太多问题。

    第二个问题是判断某个给定的可能组合是好还是坏，或者比以前的“好”解决方案更好。

    为此，你需要的不仅仅是“它是否是可能的解决方案”。

    例如，同一位教师是否在连续X周内每周工作5天？即使这是一个可行的解决方案，它可能不是一个比交替两个人更好的解决方案，使每位教师每周各做一周。哦，你没有考虑过这个吗？请记住，你正在处理的是人，而不仅仅是资源分配问题。

    即使一名教师可以连续全职工作16周，与尝试交替使用教师的解决方案相比，那也可能是一个次优解决方案，而这种平衡非常难以构建到软件中。

    总之，为这个问题提供一个好的解决方案将对许多人具有重要意义。因此，将其分解并解决不是一件容易的事情。要准备好立下一些不是100%的目标，并称它们为“足够好”。

    1
    我认为，在一开始就了解所有的限制条件是相当困难的，这需要经验和对问题的调查。我宁愿将问题分成两个独立的部分并同时开发它们。第一个部分是通用算法结构 - 描述如何填充“下一个时间表生成”，而不涉及太多“主题逻辑”的机制草案（可能是遗传算法）。第二个部分是规则提供者，具有一组约束条件，检查时间表的“正确性”- 起初可以很简单，以后再加强。 - cand
    7

    更新：根据评论...应该也要有启发式算法！

    我会选择Prolog ... 然后使用Ruby或Perl等语言将您的解决方案清理成更漂亮的形式。

    teaches(Jill,math).
teaches(Joe,history).

involves(MA101,math).
involves(SS104,history).

myHeuristic(D,A,B) :- [test_case]->D='<';D='>'.
createSchedule :- findall(Class,involves(Class,Subject),Classes),
                  predsort(myHeuristic,Classes,ClassesNew),
                  createSchedule(ClassesNew,[]).
createSchedule(Classes,Scheduled) :- [the actual recursive algorithm].

    我正在进行类似于这个问题的工作，但是使用刚才提到的相同路径。Prolog（作为一种函数式语言）确实使解决NP难问题更容易。

    1
    Prolog确实是一种表达所需问题的优秀语言，但正如您所指出的：如果不是NP-Hard，那么该问题就是NP-complete。这意味着Prolog可能不够快以进行实际实现。 - Poindexter
    3
    如果涉及到NP问题并且我们不满足于近似解，任何确定性算法都会呈指数级恶化:) - Gabriel Ščerbák
    1
    那么，目标是实现有效的启发式算法...例如，一个简单的9个任务调度算法需要3.078秒才能完成，但是使用最小窗口优先启发式算法实现相同的问题只需要0.123秒。 - Reed Debaets
    2
    哈哈，Prolog（单独）永远不会解决这个问题。抱歉用了大写字母，但我10或15年前也有同样的想法，结果彻底失败了。不是因为速度慢，而是根本无法解决任何真实世界的情况;)！ - Karussell
    6
    5
    1
    排程工具和实用程序链接已失效。 - Baran
    @Baran 使用Wayback Machine，你会找到列表。 - srijanshukla
    4
    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文，
    原文链接