3

背景

（如果您只关心算法，请跳过此步骤）

在我工作的大学里，我们系最大的麻烦之一就是课堂安排。出于说明目的和列出问题的范围，我们现在进行调度的方式如下：

  1. 教授给我们列出了他们正在教授的课程以及他们希望教授的时间段，按优先级排序（最想要到最不想要）。
  2. 行政部门向我们提供了我们可以分配的房间列表以及这些房间可供我们部门使用的时间。
  3. 我们开始将教授分配到房间，试图（起初）考虑到各个教授的偏好。
  4. 不可避免地，冲突出现了，教授们开始要求改变，计划在 30 号教授左右的某个地方分崩离析，此时我们基本上开始分配房间，只要我们能把它们放在哪里，到处都是皱巴巴的纸片，没有人高兴。（如果你想知道为什么你的课是在星期四早上 9.30 上课，但每隔一天下午 4 点上课，现在你知道了）

我被要求悄悄地调查软件是否可以更优化地做到这一点。

实际问题

是否有一种算法可以有效地调度一组资源，以满足以下标准：

  • 该算法绝不能同时将两名教授分配到同一个房间。
  • 直到每个教授都被分配了一个房间/时间，该任务才完成。
  • 该算法不必担心有太多教授来满足可用时隙的数量。（我们的资金并不充足。）
  • 该算法应尽可能尊重个别教授的调度偏好。

我觉得我不能成为第一个问这个的人。有没有一种有效的算法，或者这种问题只能被暴力破解？

4

1 回答 1

1

一段时间以来，已经有一些关于时间表和调度问题的论文。对“时间表包”这两个词的网络搜索会出现商业包和其他包。

我知道一个问题领域，尽管人们曾多次尝试寻求复杂的解决方案，但最终还是编写了非常基本的程序来实现临时解决方案——在这个领域没有明显的机构学习迹象。这样做的原因是用户需要了解程序做出决定的原因，特别是如果它未能解决问题并且他们需要放松约束。

听起来您的特定问题 - 如果它像起初听起来一样简单 - 可以通过使用http://en.wikipedia.org/wiki/Assignment_problem来解决，您可以在其中将特定课程分配给特定的房间时间段而不是代理任务。

一个程序或算法可能会受到其输入中约束的相对顺序的影响，尤其是当它遇到两个解决方案同样好的情况时。我将被包括来检查这一点，如果是这样，在将输入呈现给程序或算法之前随机重新排序输入，以尝试至少将偏见转化为随机运气。

于 2012-12-13T05:01:14.780 回答