Greedy sequential/parallel task scheduling
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) &gt; 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.