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
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.