Competitive design and analysis for machine-minimizing job scheduling problem

Mong Jen Kao*, Jian Jia Chen, Ignaz Rutter, Dorothea Wagner

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Scopus citations

Abstract

We explore the machine-minimizing job scheduling problem, which has a rich history in the line of research, under an online setting. We consider systems with arbitrary job arrival times, arbitrary job deadlines, and unit job execution time. For this problem, we present a lower bound 2.09 on the competitive factor of any online algorithms, followed by designing a 5.2-competitive online algorithm. We would also like to point out a false claim made in an existing paper of Shi and Ye regarding a further restricted case of the considered problem. To the best of our knowledge, what we present is the first concrete result concerning online machine-minimizing job scheduling with arbitrary job arrival times and deadlines.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings
PublisherSpringer Verlag
Pages75-84
Number of pages10
ISBN (Print)9783642352607
DOIs
StatePublished - 2012
Event23rd International Symposium on Algorithms and Computation, ISAAC 2012 - Taipei, Taiwan
Duration: 19 Dec 201221 Dec 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7676 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference23rd International Symposium on Algorithms and Computation, ISAAC 2012
Country/TerritoryTaiwan
CityTaipei
Period19/12/1221/12/12

Fingerprint

Dive into the research topics of 'Competitive design and analysis for machine-minimizing job scheduling problem'. Together they form a unique fingerprint.

Cite this