Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14347
For citation please use:
Main Title: Models and Algorithms for Stochastic Online Scheduling
Author(s): Megow, Nicole
Uetz, Marc
Vredeveld, Tjark
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15574
http://dx.doi.org/10.14279/depositonce-14347
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: We introduce a model for scheduling under uncertainty. In this model, we combine the main characteristics of online and stochastic scheduling in a simple and natural way. Job processing times are assumed to be stochastic, but in contrast to traditional stochastic scheduling models, we assume that jobs arrive online, and there is no knowledge about the jobs that will arrive in the future. The model incorporates both, stochastic scheduling and online scheduling as a special case. The particular setting we analyze is nonpreemptive parallel machine scheduling, with the objective to minimize the total weighted completion times of jobs. We propose simple, combinatorial online scheduling policies for that model, and derive performance guarantees that match the currently best known performance guarantees for stochastic and online parallel machine scheduling. For processing times that follow NBUE distributions, we improve upon previously best known performance bounds from stochastic scheduling, even though we consider a more general setting.
Subject(s): stochastic scheduling
online scheduling
average completion time
policies
Issue Date: 2005
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90B36 Scheduling theory, stochastic
68W40 Analysis of algorithms
68W25 Approximation algorithms
68M20 Performance evaluation; queueing; scheduling
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2005, 03
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:
Report-003-2005.pdf
Format: Adobe PDF | Size: 274.9 kB
DownloadShow Preview
Thumbnail

Item Export Bar

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