Scheduling to Minimize Flow Time Metrics

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 noncontinuous interval, for an overall amount of time equal to its processing time. All techniques that we 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 is mainly be on average flow time, while we only provide an overview of results and main open issues for average stretch and weighted flow time.