Theory of Computing ------------------- Title : Minimizing Maximum Flow-Time on Related Machines Authors : Nikhil Bansal and Bouke Cloostermans Volume : 12 Number : 14 Pages : 1-14 URL : https://theoryofcomputing.org/articles/v012a014 Abstract -------- 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.