| dc.description.abstract |
<p>Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service
measure is one of the most important research topics in both computer science theory
and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or
delay) of jobs for scheduling problems that arise in a wide range of applications.
We consider the classical model of unrelated machine scheduling and resolve several
long standing open problems; we introduce new models that capture the novel algorithmic
challenges in scheduling jobs in data centers or large clusters; we study the effect
of selfish behavior in distributed and decentralized environments; we design algorithms
that strive to balance the energy consumption and performance. </p><p>The technically
interesting aspect of our work is the surprising connections we establish between
approximation and online algorithms, economics, game theory, and queuing theory. It
is the interplay of ideas from these different areas that lies at the heart of most
of the algorithms presented in this thesis.</p><p>The main contributions of the thesis
can be placed in one of the following categories.</p><p>1. Classical Unrelated Machine
Scheduling: We give the first polygorithmic approximation algorithms for minimizing
the average flow-time and minimizing the maximum flow-time in the offline setting.
In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm
for minimizing the weighted flow-time in the resource augmentation model. Our work
introduces iterated rounding technique for the offline flow-time optimization, and
gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.</p><p>2.
Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling
problems that arise in practice, we introduce Polytope Scheduling Problem (\psp).
The \psp problem generalizes almost all classical scheduling models, and also captures
hitherto unstudied scheduling problems such as routing multi-commodity flows, routing
multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design
several competitive algorithms for the \psp problem and its variants for the objectives
of minimizing the flow-time and completion time. Our work establishes many interesting
connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant
scheduling, and queuing theoretic notion of stability and resource augmentation analysis.</p><p>3.
Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing
the total flow-time + energy in the online and resource augmentation model for the
most general setting of unrelated machines.</p><p>4. Selfish Scheduling: We study
the effect of selfish behavior in scheduling and routing problems. We define a fairness
index for scheduling policies called {\em bounded stretch}, and show that for the
objective of minimizing the average (weighted) completion time, policies with small
stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the
first linear/ convex programming duality based framework to bound the price of anarchy
for general equilibrium concepts such as coarse correlated equilibrium.</p>
|
|
