Files in this item



application/pdf3242803.pdf (3MB)Restricted to U of Illinois
(no description provided)PDF


Title:Scheduling and Admission Control
Author(s):Bunde, David Pattison
Doctoral Committee Chair(s):Jeff Erickson
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
Abstract: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.
Issue Date:2006
Description:86 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2006.
Other Identifier(s):(MiAaPQ)AAI3242803
Date Available in IDEALS:2015-09-25
Date Deposited:2006

This item appears in the following Collection(s)

Item Statistics