算法:如何在每周小时配额内安排/分配小时数？

Question

如果我每周有 5 天*(8hourWorkday-2hoursForUnexpectedWork) = 30 小时的使用时间，我如何以编程方式安排任务来填补这 30 小时？

例如，我有 5 个任务，我估计每个任务将花费以下时间:

#1:  2h
#2:  4h
#3:  6h
#4:  8h
#5: 10h

我该如何分类说:

M: #1 @ 2h + #2 @ 4h
T: #3 @ 6h
W: #4 @ 6h
H: #4 @ 2h + #5 @ 4h
F: #5 @ 6h

换句话说，如何解释“迭代和容器溢出”？

最终，我还需要能够解决超出一周的任务，例如，如果前面的示例我有一个任务 #6: 40h(本身比一周多 10 小时，并将每周总和增加到前两周需要溢出的 40 小时)。

编辑:

第二个更复杂的示例，同样有 5 个任务，这次有(可选的)星期几要求:

#1:  2h, W[0][M]
#2:  4h, W[0][T]
#3:  6h, W[0][M]
#4:  8h, W[0][F]
#5: 40h, W[0][F]

我将如何对它进行排序，比如说，

W[-1][M]: #5 @ 6h
W[-1][T]: #5 @ 6h
W[-1][W]: #5 @ 6h
W[-1][H]: #5 @ 6h
W[-1][F]: #3 @ 2h + #5 @ 4h
W[ 0][M]: #1 @ 2h + #3 @ 4h
W[ 0][T]: #2 @ 4h + #5 @ 2h
W[ 0][W]: #5 @ 6h
W[ 0][H]: #4 @ 2h + #5 @ 4h
W[ 0][F]: #4 @ 6h

最好的情况实际上是 #3 将 #1 推后一天，如下所示:

进一步说明:

• 对于一周中的每一天 (MTWHF)，填写最多 6 小时的时间。
• 如果有溢出，溢出到前一天。
• 理想情况下，这种溢出会以背包或类似优化的方式发生，这样 6 个小时就会被完整/未中断的任务尽可能地填满。
• 同样，对于溢出的日子，他们也应该将溢出调整为不破坏整个任务。

Answer 1

除非我遗漏了什么，否则这似乎是一个已解决的问题。如果任务是动态分配的(在现实环境中似乎很可能)，earliest deadline first只要利用率保持可控，日程安排就可以满足所有截止日期。由于只有在新作业进入时作业才会被抢占，这应该会导致较低的上下文切换开销和相当好的工作连续性。这是一个简单的启发式算法，在文献中引起了一定的关注，因此从等式中排除了很多猜测。

编辑:示例。

#1:  2h, W[0][M]
#2:  4h, W[0][T]
#3:  6h, W[0][M]
#4:  8h, W[0][F]
#5: 40h, W[0][F]

EDF order: #1, #3, #2, #4, #5.

Schedule: 113333332222444444445555555555555555555555555555555555555555

In days: 113333 332222 444444 445555 555555 555555 555555 555555 555555 555555

请注意，通过采用此先验调度并对 EDF 调度的结果进行后处理，我们可以在连续性方面做得更好。假设我们在一天开始时以及每当数字发生变化时都有一些上下文切换开销，则此计划会产生 13 次上下文切换，其中只有 10 次是强制性的。使用调度 #3、#1、#2、#4、#5，我们得到 12 个上下文切换。我知道这个问题最初是想尽量减少上下文切换。然而，在这方面的最佳调度算法只会通过将真正的上下文切换隐藏在强制性上下文切换(发生在一天开始时)中来比 EDF 做得更好。 EDF 的优势是保证您始终按时完成任务(如果可能的话)。这是一个权衡，但我认为 EDF 会点头。

同时考虑 rate monotonic scheduling (以你的截止日期为期限)这可能更适合静态确定的时间表，特别是如果分配的任务有任何规律性。