0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, that's a very clever proof. I was trying to use contradiction as well to prove that given the greedy schedule, it's not possible to move the task that finishes last (k in your proof) elsewhere in the order without increasing T but got lost somewhere. $\endgroup$ – Cantfindname Jun 21 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.