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 also has a constraint and only one 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.

Originally I got this question from Greedy sequential/parallel task scheduling, but that got me wondering if there is a greedy solution to this variation of the problem too, where only one task can be executed on the second half at one time as well.

My intuition tells me sort in decreasing order of ai - mi, but I can't think of a proof for this. I can't even think of a simple formula for the time it takes to finish all the tasks given some ordering of the tasks. I think that the time it takes is one of choices from $$\sum_{i=1}^k m_i + \sum_{j=k}^N a_j$$ for some $k$ where $1 \leq k \leq N$. Anyone have a closed form formula for the time given some ordering? Also is there a greedy algorithm and proof to go along with it?



Your Answer

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

Browse other questions tagged or ask your own question.