Online scheduling algorithms for broadcasting and general cost functions

Moseley, Benjamin

Permalink

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

Description

Title

Online scheduling algorithms for broadcasting and general cost functions

Author(s)

Moseley, Benjamin

Issue Date

2012-09-18T21:05:55Z

Director of Research (if dissertation) or Advisor (if thesis)

Chekuri, Chandra S.

Doctoral Committee Chair(s)

Chekuri, Chandra S.

Committee Member(s)

• Har-Peled, Sariel
• Pruhs, Kirk
• Prabhakaran, Manoj

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Scheduling
• Online algorithms
• Broadcasting
• General cost functions
• Flow time

Abstract

In this thesis we study scheduling problems that occur in the client server setting. In this setting there are a set of jobs that are sent by clients over time to a sever. There is a scheduler at the sever that determines how the jobs should be processed. The goal of the scheduler is to process the jobs in a way that optimizes the quality of service given to the clients. The quality of service is determined by some metric, which is designed for the specific needs of the system. Several systems in the real world motivate the study of the client server scheduling setting such as web servers, operating systems and load balancing in distributed computing settings. This thesis concentrates on designing online scheduling algorithms and focuses mostly on broadcast scheduling, but also considers traditional scheduling on single and multiple machines. In the broadcast setting, clients send requests for pages of information. When the sever broadcast a page, all clients requesting the page are satisfied at the same time. The broadcast setting differs from standard models because multiple requests can be satisfied by a single broadcast. To analyze our algorithms we use a worst case analysis framework. One of the main contributions of this thesis is on the design of algorithms for the online broadcast setting. We show several key algorithmic ideas and analysis techniques that prove to be useful for broadcasting. We study the algorithm Longest-Wait-First (LWF) and its variants in the broadcast setting. We show that LWF and its extensions are O(1)-speed O(1)-competitive for average flow time and the \ell_k norms of flow time for fixed k in the broadcast setting. We then extend and generalize the techniques developed in the analysis of LWF to show a (1+\eps)-speed O(poly(1/\eps))-competitive algorithm for minimizing average flow time in the broadcast setting. We also consider the minimizing the maximum weighted flow time problem and show that a natural extension of LWF to this problem does not perform well. We introduce new algorithmic ideas for this problem. To better understand minimizing the maximum weighted flow time in the broadcast model, we first consider the problem in the standard single machine and multiple identical machines settings. Here we give (1+\eps)-speed O(poly(1/\eps))-competitive algorithms. Building on these algorithms we give a new algorithm for minimizing the maximum weighted flow time in the broadcast setting and show that it is (1+\eps)-speed O(poly(1/\eps))-competitive. We then consider improving the speed-up required to give an O(1)-competitive algorithm for the \ell_k norms of flow time in the broadcast setting. Here we consider an extension of the Latest-Arrival-Processor-Sharing (LAPS) algorithm and show that it is (1+\eps)-speed O(poly(1/\eps))-competitive for all k. It is typical in scheduling theory for algorithms and analysis to be tailored for specific objective functions. However, it is valuable to ask whether or not algorithms and analysis can be unified into a single algorithm or analysis framework. Motivated by this, we introduce the general-cost-function objective. In the general cost function, the objective is to minimize \sum_{i \in [n]}w_i g(C_i - r_i) where w_i is the weight of the job, C_i is the completion time, r_i is the release time and g is some non-decreasing function of a job's flow time. The function g can be fixed to specific objectives and, hence, this framework captures most reasonable objective functions. For the general cost function, we give an algorithm that is (2+\eps)-speed O(1/\eps)-competitive in the standard single machine setting for all non-decreasing functions g. This shows that on a single machine, in the standard setting, there is indeed a single algorithm that performs well for most objectives. Further, the algorithm considered is oblivious to the function g and therefore the algorithm is (2+\eps)-speed O(1/\eps)-competitive for all objectives that fit into the framework simultaneously.

Graduation Semester

2012-08

Permalink

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

Copyright and License Information

Copyright 2012 Benjamin Moseley

Owning Collections