  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 $O(1/\epsilon^2)$-competitive algorithm
under $(1+\epsilon)$-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 {\em 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.
