direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 29-2007

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Stochastic Online Scheduling with Precedence Constraints
not available
stochastic scheduling, online optimization, precedence constraints
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.
Download as [PDF]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe