Energy-efficient scheduling and routing via randomized rounding

Bampis, E.; Kononov, A.; Letsios, D.; Lucarelli, G.; Sviridenko, M.

Авторы: Bampis E., Kononov A., Letsios D., Lucarelli G., Sviridenko M.
Журнал: Journal of Scheduling
Том: 21
Год издания: 2018
Издательство: Springer Nature
Местоположение издательства: Switzerland
Первая страница: 35
Последняя страница: 51
DOI: 10.1007/s10951-016-0500-2
Аннотация: We propose a unifying framework based on con-figuration linear programs and randomized rounding, for different energy optimization problems in the dynamic speed-scaling setting. We apply our framework to various scheduling and routing problems in heterogeneous computing and networking environments. We first consider the energy minimization problem of scheduling a set of jobs on a set of parallel speed scalable processors in a fully heterogeneous setting. For both the preemptive-nonmigratory and the preemptive-migratory variants, our approach allowsus to obtain solutions of almost the same quality as for the homogeneous environment. By exploiting the result for the preemptive-nonmigratory variant, we are able to improvethe best known approximation ratio for the single processor non-preemptive problem. Furthermore, we show that our approach allows to obtain a constant-factor approximation algorithm for the power-aware preemptive job shop scheduling problem. Finally, we consider the min-power routing problem where we are given a network modeled by an undirected graph and a set of uniform demands that have to berouted on integral routes from their sources to their destinations so that the energy consumption is minimized. We improve the best known approximation ratio for this problem.
Добавил в систему: Кононов Александр Вениаминович

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ПсковГУ
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

ИСТИНА ПсковГУ

Energy-efficient scheduling and routing via randomized roundingстатья