Speed scaling with explorable uncertainty

Evripidis Bampis, Konstantinos Dogeas, Alexander Kononov, Giorgio Lucarelli, Fanny Pascual

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование


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.

Язык оригиналаанглийский
Название основной публикацииSPAA 2021 - Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures
ИздательAssociation for Computing Machinery
Число страниц11
ISBN (электронное издание)9781450380706
СостояниеОпубликовано - 6 июл. 2021
Событие33rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2021 - Virtual, Online, Соединенные Штаты Америки
Продолжительность: 6 июл. 20218 июл. 2021

Серия публикаций

НазваниеAnnual ACM Symposium on Parallelism in Algorithms and Architectures


Конференция33rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2021
Страна/TерриторияСоединенные Штаты Америки
ГородVirtual, Online

Предметные области OECD FOS+WOS



Подробные сведения о темах исследования «Speed scaling with explorable uncertainty». Вместе они формируют уникальный семантический отпечаток (fingerprint).