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 -