Approximation results on scheduling under an uncommon constraint 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).
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?