Volume 12 (2016) Article 14 pp. 1-14
APPROX-RANDOM 2015 Special Issue
Minimizing Maximum Flow-Time on Related Machines
Revised: June 28, 2016
Published: September 14, 2016
[PDF (214K)]    [PS (965K)]    [PS.GZ (242K)]
[Source ZIP]
Keywords: related machines scheduling, maximum flow-time minimization, online algorithm, approximation algorithm
ACM Classification: F.2.2
AMS Classification: 68W25

Abstract: [Plain Text Version]

We consider the online problem of minimizing the maximum flow-time on related machines. This is a natural generalization of the extensively studied makespan minimization problem to the setting where jobs arrive over time. Interestingly, natural algorithms such as Greedy or Slow-fit that work for the simpler identical machines case or for makespan minimization on related machines, are not $O(1)$-competitive. Our main result is a new $O(1)$-competitive algorithm for the problem. Previously, $O(1)$-competitive algorithms were known only with resource augmentation, and in fact no $O(1)$-approximation was known even in the offline model.

A preliminary version of this paper appeared in the Proceedings of the 18th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'15), 2015, pp. 85--95.