贪婪顺序/并行任务调度

Question

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

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

我的直觉表明，这可以通过贪婪算法来解决，通过按降序排列任务_我 命令。

例如，给定任务：
米₁ = 3, 一个₁ = 9
米₂ = 2, 一个₂ = 7
米₃ = 6, 一个₃ = 10

最优解是排列 3, 1, 2。

然而，我很难证明贪婪的解决方案是最优的。关于如何做到这一点有什么想法吗？

Answer 1

我有一个相当混乱的证明。我相信这可以通过一些工作来清理。如果您需要我简化证明，请告诉我。

为了证明，让我们重新排列所有术语，使得$a_1 \geq a_2 \geq a_3 \ldots$. 。让 $f(1), f(2), \l点, f(N)$ 是一些时间表。任何日程安排所花费的总时间 $f$ 由下式给出。$$T(f) = \max \{m_{f(1)} + a_{f(1)}, m_{f(1)} + m_{f(2)} + a_{f(2)} ,\ldots, \sum_{i = 1}^N m_{f(i)} + a_{f(N)} \}$$.

为了矛盾起见，假设你的贪心方法不是最优解。有一些时间表 $\phi$ 这样 $T(Id) > T(\phi)$ （这里 $Id$ 是身份）。选择 $k$ 这样 $\sum_{i = 1}^k m_{i} + a_k = T(Id)$. 。让 $h$ 是最小的数，使得 $\{1,\ldots, k\} \子集 \{\phi(1), \ldots, \phi(h)\}$. 。注意 $\phi(h) \leq k$。因为 $\{1,\ldots, k\} \子集 \{\phi(1), \ldots, \phi(h)\}$, $\sum_{i = 1}^h m_{\phi(i)} \geq \sum_{i = 1}^k m_i$. 。因为 $a_1 \geq a_2 \geq \ldots$, ， 我们知道 $a_{\phi(h)} \geq a_k$. 。这意味着$$\sum_{i = 1}^k m_i + a_k \leq\sum_{i = 1}^h m_{\phi(i)} + a_{\phi(h)}$$但 $T(Id) = \sum_{i = 1}^k m_i + a_k \leq \sum_{i = 1}^h m_{\phi(i)} + a_{\phi(h)} \leq T( \phi)$. 。这是一个矛盾。