A note on on-line scheduling with precedence constraints on identical machines

We consider the on-line scheduling problem of jobs with precedence constrai nts on m parallel identical machines. Each job has a time processing requir ement, and may depend on other jobs (has to be processed after them), a job arrives only after its predecessors have been completed. The cost of an al gorithm is the time at which the last job is completed. We show lower bound s on the competitive ratio of on-line algorithms for this problem in severa l versions. We prove a lower bound of 2 - 1/m on the competitive ratio of a ny deterministic algorithm (with or without preemption) and a lower bound o f 2 - 2/(m + 1) on the competitive ratio of any randomized algorithm (with or without preemption). The lower bounds for the cases that preemption is a llowed require arbitrarily long sequences. If we use only sequences of leng th O(m2), we can show a lower bound of 2 - 2/(m + 1) on the competitive rat io of deterministic algorithms with preemption, and a lower bound of 2 - O( 1/m) on the competitive ratio of any randomized algorithm with preemption. All the lower bounds hold even for sequences of unit jobs only. The best al gorithm that is known for this problem is the well-known List Scheduling al gorithm of Graham. The algorithm is deterministic and does not use preempti on. The competitive ratio of this algorithm is 2 - 1/m. Our randomized lowe r bounds are very close to this bound (a difference of O(1/m)) and our dete rministic lower bounds match it. (C) 2000 Elsevier Science B.V. All rights reserved.