A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time

Abstract

We consider the classic scheduling problem of minimizing the total weighted flow-time on a single machine (min-WPFT), when preemption is allowed. In this problem, we are given a set of n jobs, each job having a release time rj, a processing time pj, and a weight wj. The flow-time of a job is defined as the amount of time the job spends in the system before it completes; that is, Fj = Cj – rj, where Cj is the completion time of job. The objective is to minimize the total weighted flow-time of jobs.This NP-hard problem has been studied quite extensively for decades. In a recent breakthrough, Batra, Garg, and Kumar [6] presented a pseudo-polynomial time algorithm that has an O(1) approximation ratio. The design of a truly polynomial time algorithm, however, remained an open problem. In this paper, we show a transformation from pseudo-polynomial time algorithms to polynomial time algorithms in the context of min-WPFT. Our result combined with the result of Batra, Garg, and Kumar [6] settles the long standing conjecture that there is a polynomial time algorithm with O(1)-approximation for min-WPFT.

Locations

• arXiv (Cornell University) - View - PDF
• Society for Industrial and Applied Mathematics eBooks - View - PDF