Scheduling and admission control

Ph.D. dissertation, University of Illinois at Urbana-Champaign, July 2006.
Technical report UIUCDCS-R-2006-2729.

My advisor was Jeff Erickson.

Download as gzipped postscript or pdf

This thesis includes work published independently as

• Combining Online Algorithms for Acceptance and Rejection (written jointly with Yossi Azar, Avrim Blum, and Yishay Mansour)
• Scheduling on a single machine to minimize total flow time with job rejections
• Power-aware scheduling for makespan and flow

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_Ac_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 (2+sqrt(2))/2 ≈ 1.707 in general or e/(e-1) ≈ 1.582 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.