We consider the online problem of scheduling jobs on identical machines, where jobs have precedence constraints. We are interested in the demanding setting where the jobs sizes are not known up-front, but are revealed only upon completion (the non-clairvoyant setting). Such precedence-constrained scheduling problems routinely arise in map-reduce and large-scale optimization. In this paper, we make progress on this problem. For the objective of total weighted completion time, we give a constant-competitive algorithm. And for total weighted flow-time, we give an @math -competitive algorithm under @math -speed augmentation and a natural no-surprises'' assumption on release dates of jobs (which we show is necessary in this context). Our algorithm proceeds by assigning virtual rates to all the waiting jobs, including the ones which are dependent on other uncompleted jobs, and then use these virtual rates to decide on the actual rates of minimal jobs (i.e., jobs which do not have dependencies and hence are eligible to run). Interestingly, the virtual rates are obtained by allocating time in a fair manner, using a Eisenberg-Gale-type convex program (which we can also solve optimally using a primal-dual scheme). The optimality condition of this convex program allows us to show dual-fitting proofs more easily, without having to guess and hand-craft the duals. We feel that this idea of using fair virtual rates should have broader applicability in scheduling problems.
Much less is known for flow-time problems with precedence constraints. For the offline setting on identical machines, @cite_15 give @math -approximations with @math -speedup, even for general delay functions. In the current paper, we achieve a @math -approximation with @math -speedup for flow-time. Interestingly, @cite_15 show that beating a @math -approximation for any constant @math requires a speedup of at least the optimal approximation factor of makespan minimization in the same machine environment. However, this lower bound requires different jobs with a precedence relationship to have different release dates, which is something our model disallows. (Appendix gives another lower bound showing why we disallow such precedences in the online setting.)
@cite_15
2949165180
Scheduling a set of jobs over a collection of machines is a fundamental problem that needs to be solved millions of times a day in various computing platforms: in operating systems, in large data clusters, and in data centers. Along with makespan, flow-time, which measures the length of time a job spends in a system before it completes, is arguably the most important metric to measure the performance of a scheduling algorithm. In recent years, there has been a remarkable progress in understanding flow-time based objective functions in diverse settings such as unrelated machines scheduling, broadcast scheduling, multi-dimensional scheduling, to name a few. Yet, our understanding of the flow-time objective is limited mostly to the scenarios where jobs have simple structures; in particular, each job is a single self contained entity. On the other hand, in almost all real world applications, think of MapReduce settings for example, jobs have more complex structures. In this paper, we consider two classical scheduling models that capture complex job structures: 1) concurrent open-shop scheduling and 2) precedence constrained scheduling. Our main motivation to study these problems specifically comes from their relevance to two scheduling problems that have gained importance in the context of data centers: co-flow scheduling and DAG scheduling. We design almost optimal approximation algorithms for open-shop scheduling and precedence constrained scheduling, and show hardness results.