Algorithms for flow time scheduling

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

43 Downloads (Pure)

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 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
Supervisors/Advisors
  • Blum, A., Promotor, External person
Award date1 Jan 2003
Place of PublicationPittsburgh
Publisher
Publication statusPublished - 2003

Fingerprint

Servers
Scheduling
Scheduling algorithms
Computer systems
Computer operating systems
Quality of service
Processing
Costs

Cite this

Bansal, N. (2003). Algorithms for flow time scheduling. Pittsburgh: Carnegie Mellon University.
Bansal, N.. / Algorithms for flow time scheduling. Pittsburgh : Carnegie Mellon University, 2003. 80 p.
@phdthesis{f56a28c79d7841c183b34cdf92ae98cc,
title = "Algorithms for flow time scheduling",
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 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.",
author = "N. Bansal",
year = "2003",
language = "English",
publisher = "Carnegie Mellon University",
address = "United States",
school = "Carnegie Mellon University",

}

Bansal, N 2003, 'Algorithms for flow time scheduling', Doctor of Philosophy, Carnegie Mellon University, Pittsburgh.

Algorithms for flow time scheduling. / Bansal, N.

Pittsburgh : Carnegie Mellon University, 2003. 80 p.

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

TY - THES

T1 - Algorithms for flow time scheduling

AU - Bansal, N.

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

M3 - Phd Thesis 4 Research NOT TU/e / Graduation NOT TU/e)

PB - Carnegie Mellon University

CY - Pittsburgh

ER -

Bansal N. Algorithms for flow time scheduling. Pittsburgh: Carnegie Mellon University, 2003. 80 p.