2026-10-05T22:21:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6633 2024-03-06T09:38:33Z ddc:004 open_access

A Competitive Flow Time Algorithm for Heterogeneous Clusters Under Polytope Constraints Im, Sungjin Kulkarni, Janardhan Moseley, Benjamin Munagala, Kamesh Polytope constraints average flow time multi-clusters online scheduling and competitive analysis Modern data centers consist of a large number of heterogeneous resources such as CPU, memory, network bandwidth, etc. The resources are pooled into clusters for various reasons such as scalability, resource consolidation, and privacy. Clusters are often heterogeneous so that they can better serve jobs with different characteristics submitted from clients. Each job benefits differently depending on how much resource is allocated to the job, which in turn translates to how quickly the job gets completed. In this paper, we formulate this setting, which we term Multi-Cluster Polytope Scheduling (MCPS). In MCPS, a set of n jobs arrive over time to be executed on m clusters. Each cluster i is associated with a polytope P_i, which constrains how fast one can process jobs assigned to the cluster. For MCPS, we seek to optimize the popular objective of minimizing average weighted flow time of jobs in the online setting. We give a constant competitive algorithm with small constant resource augmentation for a large class of polytopes, which capture many interesting problems that arise in practice. Further, our algorithm is non-clairvoyant. Our algorithm and analysis combine and generalize techniques developed in the recent results for the classical unrelated machines scheduling and the polytope scheduling problem [10,12,11]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sungjin Im and Janardhan Kulkarni and Benjamin Moseley and Kamesh Munagala 2016 Is Part Of LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2016.10 urn:nbn:de:0030-drops-66336 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.10 eng https://creativecommons.org/licenses/by/3.0/legalcode