Scheduling to Minimize Weighted Flow-Time.

Abstract. In this talk, we will survey known results for the off-line and the on-line problem of minimizing
weighted flow-time on unrelated machines. In this setting, we are given a set of machines and
jobs arrive over time. Each job needs to be processed by one of the machines . the running time of a
job depends on which machine it is scheduled on. The goal is to minimize the total (weighted) waiting
times of the jobs. We describe a natural linear programming relaxation for this problem which
plays a crucial role in designing algorithms for several special cases of this problem (even in the online
setting). In fact, integrality gap examples for this relaxation have also been used for proving
hardness of approximation for some special cases of this problem.