Minimizing weighted flow time

1 Introduction We consider the classic problem of scheduling a collection of dynamically arriving jobs over time so as to minimize the total weighted flow time. The flow time of a job (also known as the response time) is the total time it spends in the system, thus it is the sum of times the job is waiting and its processing time. In the case when jobs have different degrees of importance, indicated by the weight of the job, the total (average) weighted flow time is one of the simplest and natural metrics that measures the quality of service received by the jobs. For the unweighted case, a well known result [13] is that the online algorithm that at any time schedules the job with the shortest remaining processing time (SRPT) minimizes the flow time on a single machine.