International Parallel and Distributed Processing Symposium (IPDPS'03)
Scheduling to Minimize Flow Time Metrics
Nice, France
April 22-April 26
ISBN: 0-7695-1926-1
Scheduling on multiple machines is a classical problem in scheduling and dates back to the 60?s. In this survey we review work on scheduling to minimize average flow time or related metrics, on single and parallel machines. We consider an abstract model, in which a set of jobs is presented on line to a set of identical machines. Each job has a processing time and has to be processed, possibly over a non-continuous interval, for an overall amount of time equal to its processing time. All techniques we shall present have been initially applied to average flow time, while some of them have also been used to prove competitiveness results for average stretch and weighted flow time. For this reason, our focus will mainly be on average flow time, while we will only provide an overview of results and main open issues for average stretch and weighted flow time.
Index Terms:
On-line algorithms, competitive analysis, scheduling on multiple machines
Citation:
Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guido Schäfer, "Scheduling to Minimize Flow Time Metrics," ipdps, pp.223b, International Parallel and Distributed Processing Symposium (IPDPS'03), 2003