Parallel machine scheduling to minimize energy consumption

Antonios Antoniadis; Naveen Garg; Gunjan Kumar; Nikhil Kumar

Parallel machine scheduling to minimize energy consumption

Antonios Antoniadis
, Naveen Garg
, Gunjan Kumar
, Nikhil Kumar

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

Given n jobs with release dates, deadlines and processing times we consider the problem of scheduling them on m parallel machines so as to minimize the total energy consumed. Machines can enter a sleep state and they consume no energy in this state. Each machine requires L units of energy to awaken from the sleep state and in its active state the machine can process jobs and consumes a unit of energy per unit time. We allow for preemption and migration of jobs and provide the first constant approximation algorithm for this problem

Original language	English
Title of host publication	Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Pages	2758–2769
Publication status	Published - 2020
Externally published	Yes
Event	31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Hilton Salt Lake City Center, Salt Lake City, United States Duration: 5 Jan 2020 → 8 Jan 2020 Conference number: 31

Conference

Conference	31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
Abbreviated title	SODA 2020
Country/Territory	United States
City	Salt Lake City
Period	5/01/20 → 8/01/20

Keywords

n/a OA procedure

Cite this

@inproceedings{6da5fa30eba241c2a4f9b50cd01080cc,

title = "Parallel machine scheduling to minimize energy consumption",

abstract = "Given n jobs with release dates, deadlines and processing times we consider the problem of scheduling them on m parallel machines so as to minimize the total energy consumed. Machines can enter a sleep state and they consume no energy in this state. Each machine requires L units of energy to awaken from the sleep state and in its active state the machine can process jobs and consumes a unit of energy per unit time. We allow for preemption and migration of jobs and provide the first constant approximation algorithm for this problem",

keywords = "n/a OA procedure",

author = "Antonios Antoniadis and Naveen Garg and Gunjan Kumar and Nikhil Kumar",

year = "2020",

language = "English",

pages = "2758–2769",

booktitle = "Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms",

note = "31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, SODA 2020 ; Conference date: 05-01-2020 Through 08-01-2020",

}

TY - GEN

T1 - Parallel machine scheduling to minimize energy consumption

AU - Antoniadis, Antonios

AU - Garg, Naveen

AU - Kumar, Gunjan

AU - Kumar, Nikhil

N1 - Conference code: 31

PY - 2020

Y1 - 2020

N2 - Given n jobs with release dates, deadlines and processing times we consider the problem of scheduling them on m parallel machines so as to minimize the total energy consumed. Machines can enter a sleep state and they consume no energy in this state. Each machine requires L units of energy to awaken from the sleep state and in its active state the machine can process jobs and consumes a unit of energy per unit time. We allow for preemption and migration of jobs and provide the first constant approximation algorithm for this problem

AB - Given n jobs with release dates, deadlines and processing times we consider the problem of scheduling them on m parallel machines so as to minimize the total energy consumed. Machines can enter a sleep state and they consume no energy in this state. Each machine requires L units of energy to awaken from the sleep state and in its active state the machine can process jobs and consumes a unit of energy per unit time. We allow for preemption and migration of jobs and provide the first constant approximation algorithm for this problem

KW - n/a OA procedure

M3 - Conference contribution

SP - 2758

EP - 2769

BT - Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020

Y2 - 5 January 2020 through 8 January 2020

ER -

Parallel machine scheduling to minimize energy consumption

Abstract

Conference

Keywords

Fingerprint

Cite this