Algorithms for flow time scheduling

N. Bansal

Research output: ThesisPhd Thesis 4 Research NOT TU/e / Graduation NOT TU/e)

86 Downloads (Pure)


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 lp 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.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Carnegie Mellon University
  • Blum, A., Promotor, External person
Award date1 Jan 2003
Place of PublicationPittsburgh
Publication statusPublished - 2003


Dive into the research topics of 'Algorithms for flow time scheduling'. Together they form a unique fingerprint.

Cite this