Scheduling parallelizable jobs online to maximize throughput

Kunal Agrawal; Jing Li; Kefu Lu; Benjamin Moseley

doi:10.1007/978-3-319-77404-6_55

Scheduling parallelizable jobs online to maximize throughput

Kunal Agrawal, Jing Li, Kefu Lu, Benjamin Moseley

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Scopus citations

Abstract

In this paper, we consider scheduling parallelizable jobs online to maximize the throughput or profit of the schedule. In particular, a set of n jobs arrive online and each job J_i arriving at time r_i has an associated function p_i(t) which is the profit obtained for finishing job J_i at time t+ r_i. Each job can have its own arbitrary non-increasing profit function. We consider the case where each job is a parallel job that can be represented as a directed acyclic graph (DAG). We give the first non-trivial results for the profit scheduling problem for DAG jobs and show O(1)-competitive algorithms using resource augmentation.

Original language	English (US)
Title of host publication	LATIN 2018
Subtitle of host publication	Theoretical Informatics - 13th Latin American Symposium, Proceedings
Editors	Miguel A. Mosteiro, Michael A. Bender, Martin Farach-Colton
Publisher	Springer Verlag
Pages	755-776
Number of pages	22
ISBN (Print)	9783319774039
DOIs	https://doi.org/10.1007/978-3-319-77404-6_55
State	Published - 2018
Event	13th International Symposium on Latin American Theoretical Informatics, LATIN 2018 - Buenos Aires, Argentina Duration: Apr 16 2018 → Apr 19 2018

Publication series

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

Other

Other	13th International Symposium on Latin American Theoretical Informatics, LATIN 2018
Country/Territory	Argentina
City	Buenos Aires
Period	4/16/18 → 4/19/18

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-77404-6_55

Cite this

Agrawal, K., Li, J., Lu, K., & Moseley, B. (2018). Scheduling parallelizable jobs online to maximize throughput. In M. A. Mosteiro, M. A. Bender, & M. Farach-Colton (Eds.), LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings (pp. 755-776). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10807 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-77404-6_55

Agrawal, Kunal ; Li, Jing ; Lu, Kefu et al. / Scheduling parallelizable jobs online to maximize throughput. LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings. editor / Miguel A. Mosteiro ; Michael A. Bender ; Martin Farach-Colton. Springer Verlag, 2018. pp. 755-776 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6fb6b1f78cb84befb6dd518e98353252,

title = "Scheduling parallelizable jobs online to maximize throughput",

abstract = "In this paper, we consider scheduling parallelizable jobs online to maximize the throughput or profit of the schedule. In particular, a set of n jobs arrive online and each job Ji arriving at time ri has an associated function pi(t) which is the profit obtained for finishing job Ji at time t+ ri. Each job can have its own arbitrary non-increasing profit function. We consider the case where each job is a parallel job that can be represented as a directed acyclic graph (DAG). We give the first non-trivial results for the profit scheduling problem for DAG jobs and show O(1)-competitive algorithms using resource augmentation.",

author = "Kunal Agrawal and Jing Li and Kefu Lu and Benjamin Moseley",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 13th International Symposium on Latin American Theoretical Informatics, LATIN 2018 ; Conference date: 16-04-2018 Through 19-04-2018",

year = "2018",

doi = "10.1007/978-3-319-77404-6_55",

language = "English (US)",

isbn = "9783319774039",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "755--776",

editor = "Mosteiro, {Miguel A.} and Bender, {Michael A.} and Martin Farach-Colton",

booktitle = "LATIN 2018",

address = "Germany",

}

Agrawal, K, Li, J, Lu, K & Moseley, B 2018, Scheduling parallelizable jobs online to maximize throughput. in MA Mosteiro, MA Bender & M Farach-Colton (eds), LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10807 LNCS, Springer Verlag, pp. 755-776, 13th International Symposium on Latin American Theoretical Informatics, LATIN 2018, Buenos Aires, Argentina, 4/16/18. https://doi.org/10.1007/978-3-319-77404-6_55

Scheduling parallelizable jobs online to maximize throughput. / Agrawal, Kunal; Li, Jing; Lu, Kefu et al.
LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings. ed. / Miguel A. Mosteiro; Michael A. Bender; Martin Farach-Colton. Springer Verlag, 2018. p. 755-776 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10807 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Scheduling parallelizable jobs online to maximize throughput

AU - Agrawal, Kunal

AU - Li, Jing

AU - Lu, Kefu

AU - Moseley, Benjamin

N1 - Publisher Copyright: © Springer International Publishing AG, part of Springer Nature 2018.

PY - 2018

Y1 - 2018

N2 - In this paper, we consider scheduling parallelizable jobs online to maximize the throughput or profit of the schedule. In particular, a set of n jobs arrive online and each job Ji arriving at time ri has an associated function pi(t) which is the profit obtained for finishing job Ji at time t+ ri. Each job can have its own arbitrary non-increasing profit function. We consider the case where each job is a parallel job that can be represented as a directed acyclic graph (DAG). We give the first non-trivial results for the profit scheduling problem for DAG jobs and show O(1)-competitive algorithms using resource augmentation.

AB - In this paper, we consider scheduling parallelizable jobs online to maximize the throughput or profit of the schedule. In particular, a set of n jobs arrive online and each job Ji arriving at time ri has an associated function pi(t) which is the profit obtained for finishing job Ji at time t+ ri. Each job can have its own arbitrary non-increasing profit function. We consider the case where each job is a parallel job that can be represented as a directed acyclic graph (DAG). We give the first non-trivial results for the profit scheduling problem for DAG jobs and show O(1)-competitive algorithms using resource augmentation.

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

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

U2 - 10.1007/978-3-319-77404-6_55

DO - 10.1007/978-3-319-77404-6_55

M3 - Conference contribution

AN - SCOPUS:85045381226

SN - 9783319774039

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

SP - 755

EP - 776

BT - LATIN 2018

A2 - Mosteiro, Miguel A.

A2 - Bender, Michael A.

A2 - Farach-Colton, Martin

PB - Springer Verlag

T2 - 13th International Symposium on Latin American Theoretical Informatics, LATIN 2018

Y2 - 16 April 2018 through 19 April 2018

ER -

Agrawal K, Li J, Lu K, Moseley B. Scheduling parallelizable jobs online to maximize throughput. In Mosteiro MA, Bender MA, Farach-Colton M, editors, LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings. Springer Verlag. 2018. p. 755-776. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-77404-6_55

Scheduling parallelizable jobs online to maximize throughput

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this