Approximation results on scheduling under an uncommon constraint

Question

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).

Answer 1

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. http://www.springerlink.com/content/p8321031hk718413/

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

Answer 2

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).