<p>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. <a href="http://www.springerlink.com/content/p8321031hk718413/" rel="nofollow">http://www.springerlink.com/content/p8321031hk718413/</a></p>

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

CC BY-SA 3.0
2012-01-27T17:05:19.223Z
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
CC BY-SA 3.0
2012-01-27T16:42:21.287Z
2012-01-27T16:42:21.287Z
Chandra Chekuri
<p>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. </p>

<p>A communication cost is defined on an edge between two tasks $T$, $T&#39;$ as:
$$
\text{comm}(T,T&#39;)= 
\left \{ 
\begin{array}{ll}
0 &amp; \text{if alloc}(T)=\text{alloc}(T&#39;)\\
c(T,T&#39;) &amp; \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.</p>

<p>You can read the work of <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.37.111&amp;rep=rep1&amp;type=pdf" rel="nofollow">Hanen, and Munier</a> 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.</p>

<hr>

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

CC BY-SA 3.0
2012-01-29T16:23:36.557Z
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
CC BY-SA 3.0
2012-01-29T16:35:32.157Z
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
CC BY-SA 3.0
2012-01-29T11:52:03.200Z
2012-01-30T09:36:13.773Z
2012-01-30T09:36:13.773Z
Gopi
<p>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.</p>

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

<approximation-algorithms><approximation-hardness><scheduling>
Approximation results on scheduling under an uncommon constraint
aelguindy
# Approximation results on scheduling under an uncommon constraint

(Asked by: username_0 on 2012-01-27)

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

**Tags:** approximation-algorithms, approximation-hardness, scheduling

---

## 2 answers

### Answer by username_1 on 2012-01-27. Score: 3

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?

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_2 on 2012-01-29. Score: 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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.37.111&rep=rep1&type=pdf) 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).

> **Comments:**
> **username_0**: 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.  
> **username_2**: 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.  

---

