3

如果我有 5days*(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

插图#1

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

进一步澄清：

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

2 回答 2

2

除非我遗漏了什么，否则这似乎是一个已解决的问题。如果任务是动态分配的（这在现实环境中似乎很可能），那么只要利用率保持可控，最早截止日期优先调度就可以满足所有截止日期。由于只有在新工作出现时才会抢占工作，因此这应该会降低上下文切换开销和相当好的工作连续性。这是一个简单的启发式算法，在文献中受到了一些关注，因此很多猜测都被排除在外了。

编辑：示例。

#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 应该点头。

还要考虑速率单调调度（以您的截止日期为周期），这可能更适合静态确定的调度，特别是如果分配的任务有任何规律性。

于 2013-01-30T20:42:09.760 回答
1

听起来像背包问题。wiki 为这个问题提供了一些解决方案，但大多是通过动态编程解决的。

于 2013-01-24T23:26:55.863 回答