On-line scheduling with precedence constraints (Q1602711)

The on-line problem of scheduling jobs with precedence constraints on \(m\) machines, is considered. The authors concentrate in two models, the model of uniformly related machines and the model of restricted assignment. For the related machines model, it is shown a lower bound of \(\Omega(\sqrt{m})\) for the competitive ratio of deterministic and randomized on-line algorithms, with or without preemptions even for known running times. This matches the deterministic upper bound of \(O(\sqrt{m})\) given previously by Jaffe. The lower bound should be contrasted with the known bounds for jobs without precedence constraints. Specifically, without precedence constraints, if preemptions are allowed then the competitive ratio becomes \(\Theta(\log m)\), and if the running times of the jobs are known then there are \(O(1)\) competitive (preemptive and nonpreemptive) algorithms.