贪婪的顺序/并行任务调度

Question

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

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

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

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

最佳解决方案是排列3、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

对于这个问题，我得到了一个非常聪明的答案，用矛盾的方式证明了答案。斯塔克交换。

Answer 2

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

这个方程是：t=m₁a₁max（（a₂m₂-a₁），（a₃m₃-a₂），…）。

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

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

现在让我们通过归纳来证明最优解。假设n个任务的最佳答案是按a_i降序排列。然后，如果我们引入另一个a_n1和m_n1并且a_n1是a_i的最小值（我们可以通过归纳假设来假设），a_n1应该位于列表的底部。

为了证明这一点，假设a_n1去了任何其他位置，比如i。那么a_i1m_i1-a_n的值将明显大于之前的值（甚至大于a_nm_n-a_i-1）。因此，max（）函数将返回一个大于或等于其上一个值的值。

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

等式t=m₁a₁a₂m₂-a₁的值，简化为t=m₁a₂m₂。

很容易看出，a₂必须是这个等式要最小化的较小值。因此，归纳假设已被证明。