@article {17655, title = {Scheduling on Unrelated Machines under Tree-Like Precedence Constraints}, journal = {Algorithmica}, volume = {55}, year = {2009}, month = {2009///}, pages = {205 - 226}, abstract = {We present polylogarithmic approximations for the R | prec | C max and R | prec |∑ j w j C j problems, when the precedence constraints are {\textquotedblleft}treelike{\textquotedblright}{\textemdash}i.e., when the undirected graph underlying the precedences is a forest. These are the first non-trivial generalizations of the job shop scheduling problem to scheduling with precedence constraints that are not just chains. These are also the first non-trivial results for the weighted completion time objective on unrelated machines with precedence constraints of any kind . We obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment{\textemdash}this generalizes the job shop problem to these objective functions. We use the same lower bound of {\textquotedblleft}congestion + dilation{\textquotedblright}, as in other job shop scheduling approaches (e.g. Shmoys, Stein and Wein, SIAM J. Comput. 23, 617{\textendash}632, 1994 ). The first step in our algorithm for the R | prec | C max problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random-delays technique of Leighton, Maggs and Rao to the case of trees. For the special case of chains, we show a dependent rounding technique which leads to a bicriteria approximation algorithm for minimizing the flow time, a notoriously hard objective function.}, isbn = {0178-4617}, url = {http://dx.doi.org/10.1007/s00453-007-9004-y}, author = {Anil Kumar,V. and Marathe,Madhav and Parthasarathy,Srinivasan and Srinivasan, Aravind} }