Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Stochastic Online Scheduling with Precedence Constraints
Author(s): Megow, Nicole
Vredeveld, Tjark
Type: Research Paper
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.
Subject(s): stochastic scheduling
online optimization
precedence constraints
Issue Date: 2007
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2007, 29
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 198.71 kB
DownloadShow Preview

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.