Scheduling and admission control

Bunde, David Pattison

Permalink

https://hdl.handle.net/2142/11223 Copy

Description

Title

Scheduling and admission control

Author(s)

Bunde, David Pattison

Issue Date

2006-07

Keyword(s)

• algorithms
• scheduling
• admission control

Abstract

We present algorithms and hardness results for three resource allocation problems. The first is an abstract admission control problem where the system receives a series of requests and wants to satisfy as many as possible, but has bounded resources. This occurs, for example, when allocating network bandwidth to incoming calls so the calls receive guaranteed quality of service. Algorithms can have performance guarantees for this problem either with respect to acceptances or with respect to rejections. These types of guarantees are incomparable and algorithms having different types of guarantee can have nearly opposite behavior. We give two procedures for combining one algorithm of each type into a single algorithm having both types of guarantee simultaneously. Specifically, if we combine an algorithm that is c_A-competitive for acceptances with an algorithm that is c_R-competitive for rejections, the combined algorithm is O(c_A)-competitive for acceptance and O(c_A c_R)-competitive for rejections. If both the input algorithms are deterministic, then so is the combined algorithm. In addition, one of the combining procedures does not need to know the value of c_A and neither needs to know the value of c_R. The second problem we consider is scheduling with rejections, a combination of scheduling and admission control. For this problem, each job comes with a rejection cost in addition to the standard scheduling parameters. The system produces a schedule for a subset of the jobs and the schedule quality is its total flow time added to the cost for all rejected jobs. We show that, even if all jobs have the same rejection cost, no online algorithm has a competitive ratio better than (1/2)(2+sqrt{2}) in general or e/(e-1) if all jobs have the same processing time. We also give an optimal offline algorithm for unit-length jobs with arbitrary rejection costs. This leads to a pair of 2-competitive online algorithms for unit-length jobs, one when all rejection costs are equal and one when they are arbitrary. Finally, we show that the offline problem is NP-hard even when each job's rejection cost is proportional to its processing time. Our third problem is power-aware scheduling, where the processor can run at different speeds, with its energy consumption depending on the speeds selected. This results in a bicriteria problem with conflicting goals of minimizing energy consumption and giving a high-quality schedule. 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 the optimal schedule corresponding to a particular energy budget cannot be exactly computed on a machine supporting arithmetic and the extraction of roots. This hardness result holds even when scheduling equal-work jobs on a uniprocessor. We do, however, give an arbitrarily-good approximation for scheduling equal-work jobs on a multiprocessor.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11223

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections