Busy time scheduling on a bounded number of machines (Extended abstract)

Frederic Koehler, Samir Khuller

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

In this paper we consider a basic scheduling problem called the busy time scheduling problem - given n jobs, with release times rj , deadlines dj and processing times pjand m machines, where each machine can run up to g jobs concurrently, our goal is to find a schedule to minimize the sum of the “on” times for the machines. We develop the first correct constant factor online competitive algorithm for the case when g is unbounded, and give a O(log P) approximation for general g, where P is the ratio of maximum to minimum processing time. When g is bounded, all prior busy time approximation algorithms use an unbounded number of machines; note it is NP-hard just to test feasibility on fixed m machines. For this problem we give both offline and online (requiring “lookahead”) algorithms, which are O(1) competitive in busy time and O(log P) competitive in number of machines used.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings
EditorsFaith Ellen, Antonina Kolokolova, Jorg-Rudiger Sack
PublisherSpringer Verlag
Pages521-532
Number of pages12
ISBN (Print)9783319621265
DOIs
StatePublished - Jan 1 2017
Event15th International Symposium on Algorithms and Data Structures, WADS 2017 - St. John’s, Canada
Duration: Jul 31 2017Aug 2 2017

Publication series

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

Conference

Conference15th International Symposium on Algorithms and Data Structures, WADS 2017
CountryCanada
CitySt. John’s
Period7/31/178/2/17

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Busy time scheduling on a bounded number of machines (Extended abstract)'. Together they form a unique fingerprint.

  • Cite this

    Koehler, F., & Khuller, S. (2017). Busy time scheduling on a bounded number of machines (Extended abstract). In F. Ellen, A. Kolokolova, & J-R. Sack (Eds.), Algorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings (pp. 521-532). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10389 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-62127-2_44