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 mi for the guarded part, and ai 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 ai order.

For example given the tasks with:
m1 = 3, a1 = 9
m2 = 2, a2 = 7
m3 = 6, a3 = 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?

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.