Scheduling Under Power and Energy Constraints

Autor:	Dupty, Mohammed Haroon, Agrawal, Pragati, Rao, Shrisha
Rok vydání:	2016
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Distributed Parallel and Cluster Computing 68M20 90B35 F.2.2 I.1.2
Druh dokumentu:	Working Paper
Popis:	Given a system model where machines have distinct speeds and power ratings but are otherwise compatible, we consider various problems of scheduling under resource constraints on the system which place the restriction that not all machines can be run at once. These can be power, energy, or makespan constraints on the system. Given such constraints, there are problems with divisible as well as non-divisible jobs. In the setting where there is a constraint on power, we show that the problem of minimizing makespan for a set of divisible jobs is NP-hard by reduction to the knapsack problem. We then show that scheduling to minimize energy with power constraints is also NP-hard. We then consider scheduling with energy and makespan constraints with divisible jobs and show that these can be solved in polynomial time, and the problems with non-divisible jobs are NP-hard. We give exact and approximation algorithms for these problems as required. Comment: 26 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1609.07354 Zobrazit plný text záznamu View this record from Arxiv