Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14413
For citation please use:
Main Title: Online Scheduling with Bounded Migration
Author(s): Sanders, Peter
Sivadasan, Naveen
Skutella, Martin
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15640
http://dx.doi.org/10.14279/depositonce-14413
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: Consider the classical online scheduling problem where jobs that arrive one by one are assigned to identical parallel machines with the objective of minimizing the makespan. We generalize this problem by allowing the current assignment to be changed whenever a new job arrives, subject to the constraint that the total size of moved jobs is bounded by β times the size of the arriving job. For small values of β, we obtain several simple online algorithms with constant competitive ratio. We also present a linear time "online approximation scheme', that is, a family of online algorithms with competitive ratio 1+ε and constant migration factor β(ε), for any fixed ε>0.
Subject(s): scheduling
approximation
online algorithm
sensitivity analysis
Issue Date: 2008
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: 2008, 20
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-020-2008.pdf
Format: Adobe PDF | Size: 350.92 kB
DownloadShow Preview
Thumbnail

Item Export Bar

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