背景
(只关心算法的可以跳过)
在我工作的大学里,我们系最大的麻烦之一是类安排。出于说明目的并列出问题的范围,以下是我们现在进行调度的方式:
- 教授向我们提供了他们正在教授的类(class)列表以及他们希望教授的时间段,并按优先级顺序排列(最想要到最不想要)。
- 行政部门为我们提供了我们可以分配的房间列表以及这些房间可供我们部门使用的时间。
- 我们开始为教授分配房间,试图(首先)考虑到各个教授的偏好。
- 不可避免地,冲突出现了,教授们开始要求改变,而计划在 30 号教授附近的某个地方破裂了,此时我们基本上开始分配房间,只要我们能把它们放进去,弄皱的纸片到处都是,没人快乐的。 (如果你曾经想知道为什么你的课是在星期四早上 9 点 30 分,但每隔一天下午 4 点,现在你知道了)
有人要求我安静地调查软件是否可以更优化地完成此任务。
实际问题
是否有一种算法可以有效地调度一组资源以满足以下条件:
- 算法绝不能同时将两位教授分配到同一个房间。
- 直到每位教授都被分配到房间/时间后,任务才算完成。
- 该算法无需担心教授太多而无法获得足够的时间段。 (我们不是资金充足。)
- 算法应尽可能尊重个别教授的日程安排偏好。
我觉得我不能成为第一个问这个问题的人。是否有一个有效的算法来解决这个问题,或者这是只能用暴力解决的问题吗?
最佳答案
关于时间表和调度问题的论文已经有一段时间了。在网络上搜索“时间表包”这两个词会找到商业包和其他包。
我知道一个问题领域,尽管不时地尝试寻求复杂的解决方案,但人们最终还是编写了非常基本的程序来实现临时解决方案——在这个领域没有明显的机构学习迹象。声明的原因是用户需要了解程序做出决定的原因,特别是如果它无法解决问题并且他们需要放宽约束。
这听起来可能是您的特定问题 - 如果它像乍听起来那么简单 - 可以通过使用 http://en.wikipedia.org/wiki/Assignment_problem 来解决。 ,您可以将特定类(class)分配给特定的房间时间段,而不是将代理分配给任务。
程序或算法可能会受到其输入中约束的相对顺序的影响,尤其是当它遇到平局时,即两个解决方案同样好。我会被包括在内检查这一点,如果是这样,在将输入呈现给程序或算法之前随机重新排序输入,以尝试至少将偏见转化为随机运气。
关于algorithm - 是否有一种有效的算法来以既避免冲突又允许偏见的方式分配资源?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13852767/