Schedule each entree so that all entrees are completed in the shortest amount of time

Question

Lets say we have plenty people to dress up entrees, but only one chef to cook them. Each entree $E_i$, takes $c_i$ time to cook and $d_i$ time to "dress up". The dressing up of entrees can occur while other entrees are being cooked and dressed up, but we can only cook one entree at a time. How would you go about creating an algorithm to schedule each entree $E_i$ in a manner that they all get finished in the shortest amount of time?

Answer 1

The link suggested by @D.W. above put into words exactly what I was looking for, an "exchange lemma" that proves the optimality of the greedy strategy. Here it is:

Suppose we cook in the order $1,2,\ldots, n$. Let $i \in \{1,2,\ldots,n-1\}$ be the smallest integer such that $d_i<d_{i+1}$. We claim that altering the order of the cooking of dishes $i$ and $i+1$, and changing nothing else, results in an equally good or better finishing time. Let us denote $ft(k)$ as the time when dish $k$ is finished under the original ordering (and all dishes are finished at time $\max\limits_{1\leq k\leq n} ft(k)$). We also denote by $ft'(k)$ the time when dish $k$ is finished under the altered ordering.

In general, we have $$ ft(k) = \sum\limits_{j=1}^k c_j + d_k $$ since we need to finish cooking dish $k$, which happens after $1,2,\ldots, k-1$, and then finally we dress it.

For the altered ordering we have \begin{align*} ft'(i+1) &= \sum\limits_{j=1}^{i-1} c_j + c_{i+1} + d_{i+1}\\ ft'(i) &= \sum\limits_{j=1}^{i-1} c_j + c_{i+1} +c_i + d_{i} \end{align*} (the funny ordering is just to emphasize the order in which the dishes are cooked).

The following three facts are easy to prove:

1. $ft(k)=ft'(k)$ for all $k \neq i, i+1$
2. $ft'(i)\leq ft(i+1)$
3. $ft'(i+1)\leq ft(i+1)$

These three together imply that $\max\{ft'(i),ft'(i+1) \} \leq \max\{ ft(i),ft(i+1)\}$ and hence $\max ft'(k) \leq \max ft(k)$ which proves the greedy strategy.