Scheduling on Unrelated Machines under Tree-Like Precedence Constraints

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. 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—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 (e.g. Shmoys, Stein and Wein, SIAM J. Comput. 23, 617–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. A preliminary version of this paper appeared in the Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 146–157, 2005. V.S. Anil Kumar supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory, and supported in part by the Department of Energy under Contract W-7405-ENG-36. M.V. Marathe supported in part by NSF Award CNS-0626964. Part of this work was done while at the Los Alamos National Laboratory, and supported in part by the Department of Energy under Contract W-7405-ENG-36. Part of this work by S. Parthasarathy was done while at the Department of Computer Science, University of Maryland, College Park, MD 20742, and in part while visiting the Los Alamos National Laboratory. Research supported in part by NSF Award CCR-0208005 and NSF ITR Award CNS-0426683. Research of A. Srinivasan supported in part by NSF Award CCR-0208005, NSF ITR Award CNS-0426683, and NSF Award CNS-0626636.