0

我有这个问题，但不确定它属于什么算法。

我们正在尝试制作一个调度系统，用户可以在其中选择时间偏好，然后根据他们最喜欢的时间将他们分组到班级中。

假设我有 100 个用户。这些用户有他们的时间偏好。我们想将他们分成 4 -> 6 个班级，每个班级大约 20 -> 25 名学生。我的问题是

  • 如何将他们安排到他们最喜欢的课程时间，使用最少的课程？

（我们的另一个限制因素是我们拥有的教师数量和他们每周可以教的最大小时数。此外，我们希望能够有补课。例如：本周缺课的学生可以重新安排下周。 )

4

1 回答 1

2

解决这样的多目标优化问题的一种方法是找到满足一个目标的解决方案，然后使用局部搜索来尝试满足剩余的约束。

例如，如果您忽略了希望最小化使用的类数量的约束，那么您可以将其视为稳定婚姻问题（或加权二部图匹配问题）的变体 - 这具有它可以在多项式时间内求解。您对问题的变体与“医院/居民”问题最相似（根据偏好将许多居民分配到几家医院）。

这将留下几个只有少数学生的班级，因此您接下来执行本地搜索以满足“最小化班级数量”约束（如果您正确制定了稳定婚姻算法，那么您应该已经满足“没有班级超过 25 名学生”的限制） - 从那里你有两个选择：

  1. 将班级从最少学生到最多学生排序并关闭学生人数最少的班级，将被驱逐的学生重新分配到其余班级

  2. 继续考虑学生的偏好，并将课程从最不喜欢到最喜欢排序（因此，如果一个班级中有 5 名学生分配了 10 的权重，那么您将首先关闭一个有 10 名学生分配的班级它的重量为2）。

然后，您将执行另一个本地搜索以满足教师的小时数限制 - 在执行“最小化班级数量”搜索后，您将执行“教师不能教超过 X 小时”搜索，因为后一种优化将使更容易执行前一种优化。

如果生成的算法足够快，那么您可以将其随机化并运行几十次，以保存最佳结果。例如，不是首先关闭学生最少的班级，而是随机选择一个班级来关闭（加权选择，使其通常选择最小的班级——完全随机的搜索不会很好）

您可能会发现您的某个限制因素导致了很多冲突，例如，当满足教师的时间限制时，您发现您必须重新安排大部分学生。如果发生这种情况，则更改约束顺序，以便在第二遍甚至第一遍而不是第三遍时满足教师的小时数。

化妆类约束实际上可能属于约束列表的顶部（即使它的优先级较低），具体取决于其规范。例如，您可能要求补课在任何其他课之前进行（例如，周二有课的学生可以在周一补课并在他的常规课之前赶上）；尽管化妆类约束的优先级较低，但它的要求最严格，因此需要先排序。

于 2013-05-02T21:24:42.657 回答