Greedy sequential/parallel task scheduling

Question

We have N tasks that need to be scheduled for processing. Each task consists of two parts that need to executed in order. The first one is guarded by a mutex and therefore only one task can be executing this part at a time. The second part has no such constraint and any number of the tasks can be executing this at the same time. For task i we know how much time it needs to spend in each part, namely m_i for the guarded part, and a_i for the part that can be executed in parallel.

The problem is to find a permutation of the tasks such that the time needed to execute all of them is minimized.

My intuition says that this can be solved with a greedy algorithm, by scheduling the tasks in descending a_i order.

For example given the tasks with:
m₁ = 3, a₁ = 9
m₂ = 2, a₂ = 7
m₃ = 6, a₃ = 10

The optimal solution is the permutation 3, 1, 2.

However, I have trouble proving that the greedy solution is optimal. Any ideas on how to do that?

Answer 1

I have a pretty messy proof. I'm sure this can be cleaned up with a bit of work. Let me know if you need me to simplify the proof.

For the sake of the proof, lets rearrange all the terms such that $a_1 \geq a_2 \geq a_3 \ldots$. Let $f(1), f(2), \ldots, f(N)$ be some schedule. The total time spent for any schedule $f$ is given by the following. $$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)} \}$$.

For the sake of contradiction, suppose that your greedy method is not the optimal solution. There exists some schedule $\phi$ such that $T(Id) > T(\phi)$ (here $Id$ is the identity). Choose $k$ such that $\sum_{i = 1}^k m_{i} + a_k = T(Id)$. Let $h$ be the smallest number such that $\{1,\ldots, k\} \subset \{\phi(1), \ldots, \phi(h)\}$. Note that $\phi(h) \leq k$. Because $\{1,\ldots, k\} \subset \{\phi(1), \ldots, \phi(h)\}$, $\sum_{i = 1}^h m_{\phi(i)} \geq \sum_{i = 1}^k m_i$. Because $a_1 \geq a_2 \geq \ldots$, we know that $a_{\phi(h)} \geq a_k$. This means that $$\sum_{i = 1}^k m_i + a_k \leq\sum_{i = 1}^h m_{\phi(i)} + a_{\phi(h)}$$ But $T(Id) = \sum_{i = 1}^k m_i + a_k \leq \sum_{i = 1}^h m_{\phi(i)} + a_{\phi(h)} \leq T(\phi)$. This is a contradiction.