Online scheduling algorithms for average flow time and its variants
Sungjin Im · 2012
This dissertation focuses on scheduling problems that are found in a client-server setting where multiple clients and one server (or multiple servers) are the participating entities. Clients send their requests to the server(s) over time, and the server needs to satisfy the requests using its resources. This setting is prevalent in many applications including multiuser operating systems, web servers, database servers, and so on. A natural objective for each client is to minimize the flow time (or equivalently response time) of her request, which is defined as its completion time minus its release time. The server, with multiple requests to serve in its queue, has to prioritize the requests for scheduling. Inherently, the server needs a global scheduling objective to optimize. We mainly study the scheduling objective of minimizing `k-norms of flow time of all requests, where 1 ≤ k < ∞. These objectives can be used to balance average performance and fairness. A popular performance measure for online scheduling algorithms is competitive