An important objective function in the scheduling literature is to minimize the sum of weighted flow times. We are given a set of jobs, where each job is characterized by a release time, a processing time, and a weight. Our goal is to find a preemptive schedule on a single machine that minimizes the sum of the weighted flow times of the jobs, where the flow time of a job is the time between its completion time and its release time. We answer this question in the affirmative and present a polynomial time (1 + 𝜀)-approximation algorithm for weighted flow time on a single machine. We use a reduction of the problem to a geometric covering problem, which was introduced in previous approaches and which loses only a factor of 1+𝜀 in the approximation ratio. However, unlike the previous algorithm, we solve the resulting instances of the covering problem exactly, rather than losing a factor 2 + 𝜀. Key for this is to identify and exploit structural properties of instances of that problem covering problem which arise in the reduction from weighted flow time.
This talk is based on joint work with Lars Rohwedder and Andreas Wiese.