Balancing Flow Time and Energy Consumption

Sami Davies, Samir Khuller, Shirley Zhang

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

2 Scopus citations

Abstract

In this paper, we study the following batch scheduling model: find a schedule that minimizes total flow time for n uniform length jobs, with release times and deadlines, where the machine is only actively processing jobs in at most k synchronized batches of size at most B. Prior work on such batch scheduling models has considered only feasibility with no regard to the flow time of the schedule. However, algorithms that minimize the cost from the scheduler's perspective - such as ones that minimize the active time of the processor - can result in schedules where the total flow time is arbitrarily high [15]. Such schedules are not valuable from the perspective of the client. In response, our work provides dynamic programs which minimize flow time subject to active time constraints. Our main contribution focuses on jobs with agreeable deadlines; for such job instances, we introduce dynamic programs that achieve runtimes of O(B · k · n) for unit jobs and O(B · O(B · n5) for uniform length jobs. These results improve upon our modification of a different, classical dynamic programming approach by Baptiste. While the modified DP works when deadlines are non-agreeable, this solution is more expensive, with runtime O(B · k2 · n7) [7].

Original languageEnglish (US)
Title of host publicationSPAA 2022 - Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Pages369-380
Number of pages12
ISBN (Electronic)9781450391467
DOIs
StatePublished - Jul 11 2022
Event34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2022 - Philadelphia, United States
Duration: Jul 11 2022Jul 14 2022

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Conference

Conference34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2022
Country/TerritoryUnited States
CityPhiladelphia
Period7/11/227/14/22

Keywords

  • dynamic programming
  • energy minimization
  • scheduling

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Balancing Flow Time and Energy Consumption'. Together they form a unique fingerprint.

Cite this