Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Speed scaling with explorable uncertainty. / Bampis, Evripidis; Dogeas, Konstantinos; Kononov, Alexander et al.
SPAA 2021 - Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, 2021. p. 83-93 (Annual ACM Symposium on Parallelism in Algorithms and Architectures).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Speed scaling with explorable uncertainty
AU - Bampis, Evripidis
AU - Dogeas, Konstantinos
AU - Kononov, Alexander
AU - Lucarelli, Giorgio
AU - Pascual, Fanny
N1 - Publisher Copyright: © 2021 ACM.
PY - 2021/7/6
Y1 - 2021/7/6
N2 - In this paper, we introduce a model for the speed scaling setting in the framework of explorable uncertainty. In the model, each job has a release time, a deadline and an unknown workload that can be revealed to the algorithm only after executing a query that induces a given additional job-dependent load. Alternatively, the job may be executed without any query, but in that case its workload is equal to a given upper bound. This assumption is motivated for instance in applications like code optimization, or file compression. We study the problem of minimizing the overall energy consumption for executing all the jobs in their time windows. We also consider the related problem of minimizing the maximum speed used by the algorithm. We present lower and upper bounds for both the offline case, where all the jobs are known in advance, and the online case, where the jobs arrive over time. We start with the single machine setting and we finally deal with the more general case where multiple identical parallel machines are available.
AB - In this paper, we introduce a model for the speed scaling setting in the framework of explorable uncertainty. In the model, each job has a release time, a deadline and an unknown workload that can be revealed to the algorithm only after executing a query that induces a given additional job-dependent load. Alternatively, the job may be executed without any query, but in that case its workload is equal to a given upper bound. This assumption is motivated for instance in applications like code optimization, or file compression. We study the problem of minimizing the overall energy consumption for executing all the jobs in their time windows. We also consider the related problem of minimizing the maximum speed used by the algorithm. We present lower and upper bounds for both the offline case, where all the jobs are known in advance, and the online case, where the jobs arrive over time. We start with the single machine setting and we finally deal with the more general case where multiple identical parallel machines are available.
KW - Explorable uncertainty
KW - Scheduling
KW - Speed scaling
UR - http://www.scopus.com/inward/record.url?scp=85109511697&partnerID=8YFLogxK
U2 - 10.1145/3409964.3461812
DO - 10.1145/3409964.3461812
M3 - Conference contribution
AN - SCOPUS:85109511697
T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures
SP - 83
EP - 93
BT - SPAA 2021 - Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures
PB - Association for Computing Machinery
T2 - 33rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2021
Y2 - 6 July 2021 through 8 July 2021
ER -
ID: 33988624