Nikhil Bansal

Algorithms for Flow Time Scheduling Degree Type: Ph.D. in Computer Science
Advisor(s): Avrim Blum
Graduated: December 2003

Abstract:

We study scheduling algorithms for problems arising in client-server systems. In the client-server setting, there are multiple clients that submit requests for service to the server(s) over time. Typical examples of such systems include operating systems, web-servers and database query servers. As there could be multiple clients requesting a service, the goal of a scheduling algorithm is to provide service to the clients in some reasonable way. A natural measure of the quality of service received by a client is its flow time, defined as the time since the client submits a request until it is completed. In this thesis, we study some fundamental problems related to minimizing flow time and its variants. These include  L_p norms of flow time, weighted flow time, stretch (flow time divided by its service requirement) and completion time. We consider these problems in various settings, such as online, offline, scheduling when the processing requirements are unknown and scheduling when jobs can be rejected at some cost.

Thesis Committee:
Avrim Blum (Chair)
Bruce Maggs
R. Ravi
Kirk Pruhs (University of Pittsburgh)

Randy Bryant, Head, Computer Science Department
James Morris, Dean, School of Computer Science

Keywords:
Approximation algorithms, on-line algorithms, scheduling, flow time, non-clairvoyant scheduling