Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14371
For citation please use:
Main Title: Approximation Results for Preemptive Stochastic Online Scheduling
Author(s): Megow, Nicole
Vredeveld, Tjark
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15598
http://dx.doi.org/10.14279/depositonce-14371
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: We present first constant performance guarantees for preemptive stochastic scheduling to minimize the sum of weighted completion times. For scheduling jobs with release dates on identical parallel machines we derive policies with a guaranteed performance ratio of 2 which matches the currently best known result for the corresponding deterministic online problem.
Subject(s): scheduling
total weighted completion time
preemptive
approximation
stochastic dynamic optimization
online optimization
Issue Date: 2006
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: 2006, 08
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-008-2006.pdf
Format: Adobe PDF | Size: 227.96 kB
DownloadShow Preview
Thumbnail
Report-008-2006.ps
Format: Postscript | Size: 400.27 kB
Download

Item Export Bar

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