Minimizing Average Flow-time: Upper and Lower Bounds

We consider the problem of minimizing average flow time on multiple machines when each job can be assigned only to a specified subset of the machines. This is a special case of scheduling on unrelated machines and we show that no online algorithm can have a bounded competitive ratio. We provide an O(log P)-approximation algorithm by modifying the single-source unsplittable flow algorithm of Dinitz, et. al. Here P is the ratio of the maximum to the minimum processing times. We establish an Omega(log P)-integrality gap for our LP-relaxation and use this to show an Omega(log P/log log P) lower bound on the approximability of the problem. We then extend the hardness results to the problem of minimizing flow time on parallel machines and establish the first non-trivial lower bounds on the approximability; we show that the problem cannot be approximated to within Omega(radiclog P/log log P).

Authors

• Naveen Garg 0001
• Amit Kumar 0001

Keywords

• Scheduling algorithm
• Polynomials
• Approximation algorithms
• Computer science
• Parallel machines
• Security
• Single machine scheduling
• Web server
• Fluid flow measurement
• Time measurement
• Lower Bound
• Processing Time
• Flow Time
• Multiple Machine
• Online Algorithm
• Hardness Results
• Competitive Ratio
• Time Step
• Unit Time
• Linear Programming
• End Of Phase
• Unit Volume
• Intensity Time
• Time Slot
• Perfect Match
• Job Type
• Algorithm Structure
• Release Date
• Fractional Solution
• Job Scheduling
• Outgoing Edges
• Integral Solution
• Incoming Edges
• Job Processing
• Phase 0
• Maximum Demand
• Size Matching
• Polylogarithmic