Scheduling and Admission Control

Our third problem is power-aware scheduling, where the processor can run at different speeds, with its energy consumption depending on the speeds selected. If schedule quality is measured with makespan, we give linear-time algorithms to compute all non-dominated solutions for the general uniprocessor problem and for the multiprocessor problem when every job requires the same amount of work. We also show that the multiprocessor problem becomes NP-hard when jobs can require different amounts of work. If schedule quality is measured with total flow time, we show that finding the optimal schedule for a particular energy budget is impossible. We do, however, give an arbitrarily-good approximation for scheduling equal-work jobs on a multiprocessor.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2015

Author dc:creator

• Bunde, David Pattison

Contributors dc:contributor

• Jeff Erickson

• Computer Science

Language dc:language

eng

Identifier

(MiAaPQ)AAI3242803

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/81731