ruby-on-rails - ruby/rails 中的预约调度

Question

我正在使用 Rails 开发调用中心软件，需要为可以处理客户调用的代理安排约会。话虽如此，调用中心软件需要确保我尽可能利用整个座席的日程安排约会，从而为最少数量的漏洞留出空间(座席没有预约)。

给定代理人的日程安排，例如给定一天的上午 9:00 到下午 5:30，午休时间为下午 1:00 到下午 1:30，午休时间为 30 分钟，我需要安排不同时长的约会，一些60分钟，大约90分钟。

如果出于某种原因，午休时间在日程安排中留下了一些空缺，我应该可以将午休时间移动 30 分钟 +/-，因此可以将午休时间从 1:00 PM - 1:30 改为 1:30 PM -下午 2:00 或中午 12:30 - 下午 1:00。

我开始创建午休时间作为一种约会，它将提供移动 starts_at 和 finishes_at 属性的灵 active 。约会是 60 分钟或 90 分钟，是 30 分钟的倍数，午餐也是 30 分钟，我开始将代理时间表拆分为每个 30 分钟的时段。

因此，对于给定一天的给定代理，查看他的日程安排，我实例化了一个时隙数组，每个时隙的持续时间为 30 分钟，starts_at 和 finishes_at 属性类似于 9:00AM - 9:30AM，9:30AM - 10 :00AM 等

我需要一些帮助来遍历这一系列的约会时段，并根据 60 或 90 分钟的约会时间拉出 2 个连续的时段或 3 个连续的时段，请记住我应该能够将午餐移动 +/- 30分钟。

非常感谢任何帮助。

Answer 1

查看您的问题:

1. 预约时长为 60 或 90 分钟。
2. 午餐时间可以在 12:30-2:00 之间，间隔 90 分钟

我们希望尽量减少没有约会的分钟数。

现在，您需要填写一个时间间隔，即上午 9:00 到下午 5:30。假设约会在 9:00-5:30 之间，我们可以使用贪心算法根据最早完成时间 (source) 和您的附加约束进行间隔调度。

基本上算法如下(伪)

Let R be the set of all appointments
Let R11 be the set of appointments from R before 12:30 that are compatible with 12:30-1:00 and R12 be the set of appointments from R after 1:00 that are compatible with 12:30-1:00
Let R21 be the set of appointments from R before 1:00 that are compatible with 1:00-1:30 and R22 be the set of appointments from R after 1:30 that are compatible with 1:00-1:30
Let R31 be the set of appointments from R before 1:30 that are compatible with 1:30-2:00 and R32 be the set of appointments from R after 2:00 that are compatible with 1:30-2:00

Let R1Comb = findSet(R11) + 12:30-1:00 + findSet(R12)
Let R2Comb = findSet(R21) + 1:00-1:30 + findSet(R22)
Let R3Comb = findSet(R31) + 1:30-2:00 + findSet(R32)

Function findSet(R) 
    Let A be the time interval to fill    
    While R is not empty
        Choose a request r in R that has the smallest finishes_at
        Add r to A
        Remove all appointments in R that are not compatible with r
    EndWhile
    Return A
EndFunction

Return the R that has the smallest amount of holes in R1Comb, R2Comb, R3Comb

这个算法利用了一些概念

1. 约会 r1 与 r2 如果重叠则不兼容。
2. 因为#1，我们知道 i=1,2,3 的 Ri1/Ri2 不会相互冲突。因为如果 Ri2 的约会与 Ri1 不兼容，那么它也与午餐时间不兼容，这是一个矛盾，因为我们把不兼容的约会都去掉了。
3. 一旦我们拆分了约会集，接下来就是解决 2 个调度问题，这两个问题可以贪婪地解决。

这个算法还是O(n log n)因为你在做贪心算法6次(一个常数)，每次贪心迭代都是O(n log n)，前几行和最后一行是所有 O(n)。

人们写关于日程安排的论文，这不是一个简单的问题。我建议你看看 http://www.asap.cs.nott.ac.uk/watt/resources/university.html以获得更好的理解。

祝你好运:)