TY - GEN

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

AU - Koehler, Frederic

AU - Khuller, Samir

N1 - Funding Information:
Full version: http://math.mit.edu/~fkoehler/busytime.pdf . Research supported by CCF 1217890 and CNS 1262805.
Publisher Copyright:
© Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85025156420&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85025156420&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-62127-2_44

DO - 10.1007/978-3-319-62127-2_44

M3 - Conference contribution

AN - SCOPUS:85025156420

SN - 9783319621265

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 521

EP - 532

BT - Algorithms and Data Structures - 15th International Symposium, WADS 2017, Proceedings

A2 - Ellen, Faith

A2 - Kolokolova, Antonina

A2 - Sack, Jorg-Rudiger

PB - Springer Verlag

T2 - 15th International Symposium on Algorithms and Data Structures, WADS 2017

Y2 - 31 July 2017 through 2 August 2017

ER -