ALCOMFT-TR-03-109

Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guido Schäfer and Tjark Vredeveld
Scheduling to minimize flow time metrics
Rome and MPI. Work packages 2 and 4. November 2003.

Abstract: 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.

Postscript file: ALCOMFT-TR-03-109.ps.gz (90 kb).