贪心sequential/parallel任务调度

Question

我们有 N 个任务需要安排处理。每个任务由两部分组成，需要按顺序执行。第一个由互斥体保护，因此一次只能有一个任务执行这部分。第二部分没有这样的约束，任何数量的任务都可以同时执行。对于任务i，我们知道每个部分需要花费多少时间，即m_i用于保护部分，a_i 对于可以并行执行的部分。

问题是找到任务的排列，使执行所有任务所需的时间最小化。

我的直觉告诉我，这可以通过贪心算法解决，即按 _i 降序安排任务。

例如给定任务：
m₁ = 3, a₁ = 9
m₂ = 2, a₂ = 7
m₃ = 6, a₃ = 10

最佳解决方案是排列 3、1、2，其中任务重叠如下（加号是第 1 部分花费的时间，减号是第 2 部分花费的时间）：

3 ++++++---------- (6, 10)
1       +++--------- (3,9)
2          ++------- (2,7)
Total time needed: 6+3+2+7: 18

任何其他排列都需要更长的总时间，例如：

1 +++--------- (3,9)
2    ++------- (2,7)
3      ++++++---------- (6, 10)
Total time needed: 3+2+6+10: 21

但是，我无法证明贪心解是最优的。关于如何做到这一点有什么想法吗？

Answer 1

为了解决这个问题，让我们先写一个等式来计算N个任务所花费的总时间。

这个等式是： t = m₁ + a₁ + max((a₂ + m₂ - a₁), (a₃ + m₃ - a₂), ...).

这个等式的第一部分（m₁ + m₂ + ...）是第一个需要的时间任务

等式的第二部分更复杂。简单地说，max() 计算不与第一个任务重叠的最大任务时间量（在您的示例中，这个最大时间是 9）。

现在让我们通过归纳来证明最优解。假设 n 个任务的最佳答案是按 _i 降序排列。那么，如果我们引入另一个a_n+1和m_n+1和a_n+1是 a_i 的最小值（我们可以通过归纳假设来假设），a_n+1 应该排到列表的底部。

为了证明这一点，假设a_n+1去了任何其他位置，比如i。那么 a_i+1 + m_i+1 - a_n 的值显然会更大比以前（甚至大于 a_n + m_n - a_i-1） .因此，max() 函数将 return 一个大于或等于其先前值的值。

现在我们必须证明 n = 2 的归纳假设。假设我们有 a₁ 和 a₂。

方程的值t = m₁ + a₁ + a₂ + m₂ - a₁，简化为 t = m₁ + a₂ + m₂ 现在很有趣。

很容易看出 a₂ 必须是要使该方程最小化的较小值。因此，归纳假设得到证明。

Answer 2

对于这个问题，我得到了一个非常聪明的答案，并通过反证法证明了 cs.stackexchange。

Greedy sequential/parallel task scheduling