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 where the tasks overlap as follows (pluses being the time spent in part 1 and minuses being the time spent in part 2):
3 ++++++---------- (6, 10)
1 +++--------- (3,9)
2 ++------- (2,7)
Total time needed: 6+3+2+7: 18
Any other permutation gives a higher total time needed, e.g.:
1 +++--------- (3,9)
2 ++------- (2,7)
3 ++++++---------- (6, 10)
Total time needed: 3+2+6+10: 21
However, I have trouble proving that the greedy solution is optimal. Any ideas on how to do that?
I got a pretty clever answer for this question with a proof by contradiction over as cs.stackexchange.