Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am looking for any approximation results for unrelated multiprocessor scheduling problem with precedence constraints (minimizing makespan), i.e. $R|prec|C_{max}$, with the constraint that some tasks need to run together on the same processor. I searched a lot and the closest constraint I could find was that some tasks have to run on certain processors. I need to group tasks in classes such that each class must run on the same processor. Note that the precedence constraints prevent collapsing each class into a single big task.

I would like to find any literature on the problem (or any non-trivial relaxation, for example removing the precedence constraints will allow the classes of tasks to be treated as one task).

share|cite|improve this question

Even without the additional constraints you have the unrelated machine scheduling problem with precedence constraints is not well understood. If I am not mistaken nothing better than a polynomial factor approximation is known. It is an important open problem in approximation algorithms for scheduling problems. Some positive results are known when the precedence constraints form a tree. See the following paper.

Can you solve your problem in the simpler case when the machines are identical or related?

share|cite|improve this answer
No, I can't solve it either. I am actually looking for any results, even on identical machines. I just want to know if the constraint has been studied before, even a keyword to search by. – aelguindy Jan 27 '12 at 17:05

Have you tried to look for what already existed in the field of Scheduling with Communication Cost? If you choose some of the communication cost to be $+\infty$, then it seems to me that it is exactly your problem.

A communication cost is defined on an edge between two tasks $T$, $T'$ as: $$ \text{comm}(T,T')= \left \{ \begin{array}{ll} 0 & \text{if alloc}(T)=\text{alloc}(T')\\ c(T,T') & \text{otherwise.} \end{array} \right. $$ Where the function $c$ is a well-defined cost function (in your case it could be $0$ or $+\infty$, depending on your constraints), and $\text{alloc}(T)$ is the function that states the processor on which $T$ is scheduled.

You can read the work of Hanen, and Munier which is more adapted for small communication delays, however since in the general case your communication delays are small, it might be possible to adapt their algorithm. In the worst case you can check on scholar who cites their paper, it may be a good start for bibliographical work.

You could also check the key-words scheduling with security constraints; it seems that your problem could be justified with security reasons (when a computation has been done, you do not want some part of the result to be communicated in case someone were to intercept the communication). So maybe you could check in some security-based conferences (such as SAFECOMP).

share|cite|improve this answer
I like the idea, but I don't think this is quite true. If I understand correctly, communication costs are defined as a function on pairs of processors. If two tasks need to be on the same processor, then it should not imply that other tasks cannot be on different ones. +1 for the security constraints! It did not cross my mind. – aelguindy Jan 29 '12 at 16:23
Well you can have some communication cost set to epsilon and some communication costs set to $+\infty$. Communication costs are defined as costs set on the precedence constraints of your DAGs, so they are dependent on the tasks rather than the processors. – Gopi Jan 29 '12 at 16:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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