Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints

TitleScheduling on Unrelated Machines Under Tree-Like Precedence Constraints
Publication TypeBook Chapters
Year of Publication2005
AuthorsKumar V, Marathe M, Parthasarathy S, Srinivasan A
EditorChekuri C, Jansen K, Rolim J, Trevisan L
Book TitleApproximation, Randomization and Combinatorial Optimization. Algorithms and TechniquesApproximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Series TitleLecture Notes in Computer Science
Volume3624
Pagination609 - 609
PublisherSpringer Berlin / Heidelberg
ISBN Number978-3-540-28239-6
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 “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.

URLhttp://dx.doi.org/10.1007/11538462_13