Improved Online Algorithm for Weighted Flow Time

We discuss one of the most fundamental scheduling problem of processing jobs on a single machine to minimize the weighted flow time (weighted response time). Our main result is a O(log P)-competitive algorithm, where P is the maximum-to-minimum processing time ratio, improving upon the O(log 2 P)competitive algorithm of Chekuri, Khanna and Zhu (STOC 2001). We also design a O(log D)-competitive algorithm, where D is the maximum-to-minimum density ratio of jobs. Finally, we show how to combine these results with the result of Bansal and Dhamdhere (SODA 2003) to achieve a O(log(min(P, D, W)))competitive algorithm (where W is the maximum-tominimum weight ratio), without knowing P, D, W in advance. As shown by Bansal and Chan (SODA 2009), no constant-competitive algorithm is achievable for this problem.

Authors

• Yossi Azar
• Noam Touitou

Keywords

• Bars
• Containers
• Approximation algorithms
• Visualization
• Liquids
• Indexes
• Computer science
• Flow Time
• Online Algorithm
• Weighted Flow Time
• Processing Time
• Density Ratio
• Single Machine
• Competitive Algorithm
• Job Processing
• Optimization Algorithm
• Maximum Ratio
• Weight Categories
• Power-of-two
• Static Algorithm
• Set Of Bins
• Competitive Ratio
• Online
• Scheduling