TY - CHAP T1 - Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints T2 - Approximation, Randomization and Combinatorial Optimization. Algorithms and TechniquesApproximation, Randomization and Combinatorial Optimization. Algorithms and Techniques Y1 - 2005 A1 - Kumar, V. A1 - Marathe,Madhav A1 - Parthasarathy,Srinivasan A1 - Srinivasan, Aravind ED - Chekuri,Chandra ED - Jansen,Klaus ED - Rolim,José ED - Trevisan,Luca AB - We present polylogarithmic approximations for the R | prec | C max and R | prec |∑ j w j C j problems, when the precedence constraints are “treelike” – i.e., when the undirected graph underlying the precedences is a forest. We also obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment – this generalizes the job shop problem to these objective functions. We use the same lower bound of “congestion+dilation”, as in other job shop scheduling approaches. 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 weighted completion time, we show a certain type of reduction to the makespan problem, which dovetails well with the lower bound we employ for the makespan problem. For the special case of chains, we show a dependent rounding technique which leads to improved bounds on the weighted completion time and new bicriteria bounds for the flow time. JA - Approximation, Randomization and Combinatorial Optimization. Algorithms and TechniquesApproximation, Randomization and Combinatorial Optimization. Algorithms and Techniques T3 - Lecture Notes in Computer Science PB - Springer Berlin / Heidelberg VL - 3624 SN - 978-3-540-28239-6 UR - http://dx.doi.org/10.1007/11538462_13 ER -