Stochastic Online Scheduling with Precedence Constraints

Abstract

We consider the classical non-preemptive scheduling problem of processing jobs with precedence constraints on parallel machines with the objective to minimize the sum of (weighted) completion times. We discuss a reasonable online model and give lower and upper bounds on the competitive ratio for scheduling without job preemptions. These are the first investigation on online scheduling with precedence constraints for the considered objective function. We show matching bounds for scheduling on a single machine and corresponding bounds for scheduling on parallel machines. Our results hold also in a the more general stochastic online scheduling model where, in addition to the limited information about the jobset, processing times are uncertain. In particular, we derive an n-approximation for the stochastic online scheduling problem P|prec|E(sum w_jC_j). This bound is not constant but it is a first performance guarantee for non-preemptive stochastic scheduling that is independent of processing time distributions.