Brief announcement: Scheduling parallelizable jobs online to maximize throughput

Kunal Agrawal, Jing Li, Kefu Lu, Benjamin Moseley

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

Abstract

We consider scheduling parallelizable jobs online to maximize the throughput or profit of the schedule. A set of n jobs arrive online and each job Ji has an associated function pi (t ), the profit obtained for finishing job Ji at time t. Each job has its own arbitrary nonincreasing 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 showing O(1)-competitive algorithms using resource augmentation.

Original languageEnglish (US)
Title of host publicationSPAA 2017 - Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Pages87-89
Number of pages3
ISBN (Electronic)9781450345934
DOIs
StatePublished - Jul 24 2017
Externally publishedYes
Event29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017 - Washington, United States
Duration: Jul 24 2017Jul 26 2017

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures
VolumePart F129316

Other

Other29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2017
CountryUnited States
CityWashington
Period7/24/177/26/17

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Brief announcement: Scheduling parallelizable jobs online to maximize throughput'. Together they form a unique fingerprint.

Cite this