On-line scheduling with precedence constraints

We consider the on-line problem of scheduling jobs with precedence con-straints on m machines. We concentrate in two models, the model of uniformly related machines and the model of restricted assignment. For the related ma-chines model, we show a lower bound of p 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( p m) given by Jae. The lower bound should be contrasted with the known bounds for jobs without precedence constraints. Specically, without prece-dence constraints, if we allow preemptions then the competitive ratio becomes (logm), and if the running times of the jobs are known then there are O(1) competitive (preemptive and non-preemptive) algorithms. We also consider the restricted assignment model. For the model with con-sistent precedence constraints, we give a (randomized) lower bound of (logm) with or without preemptions. We show that a (deterministic, non-preemptive) greedy algorithm is optimal up to a constant factor for this model i.e. O(logm) competitive. However, for general precedence constraints, we show a lower bound of m which is easily matched by a greedy algorithm