2026-07-23T08:46:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5296 2024-03-06T10:36:15Z ddc:004 open_access

Minimizing Maximum Flow-time on Related Machines Bansal, Nikhil Cloostermans, Bouke Related machines scheduling Maximum flow-time minimization On-line algorithm Approximation algorithm 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 case. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikhil Bansal and Bouke Cloostermans 2015 Is Part Of LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2015.85 urn:nbn:de:0030-drops-52964 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.85 eng https://creativecommons.org/licenses/by/3.0/legalcode