Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14270
For citation please use:
Main Title: On-line scheduling to minimize average completion time revisited
Author(s): Megow, Nicole
Schulz, Andreas S.
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15497
http://dx.doi.org/10.14279/depositonce-14270
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith's ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms.
Subject(s): scheduling
on-line algorithms
approximation algorithms
deterministic
competitive analysis
average completion time
Issue Date: 2003
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: 2003, 22
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-022-2003.pdf
Format: Adobe PDF | Size: 142.75 kB
DownloadShow Preview
Thumbnail
Report-022-2003.ps.gz
Format: Unknown | Size: 74.82 kB
Download

Item Export Bar

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