Online load balancing on related machines

Conference Paper

We give a constant-competitive algorithm for the problem of assigning jobs online to machines with non-uniform speed (called related machines) so as to optimize any ℓq-norm of the machine loads. Previously, such a result was only known for the special case of the makespan, or ℓ∞. norm. We also extend these results to obtain tight bounds for the problem of vector scheduling on related machines, where no results were previously known even for the makespan norm. To obtain our results, we employ a convex relaxation of the ℓq-norm objective and use a continuous greedy algorithm to solve this convex program online. To round the fractional solution, we then use a novel restructuring of the instance that we call machine smoothing. This is a generic tool that reduces a problem on related machines to a set of problem instances on identical machines, and we hope it will be useful in other settings with non-uniform machine speeds as well.

Full Text

Duke Authors

Cited Authors

  • Im, S; Panigrahi, D; Kell, N; Shadloo, M

Published Date

  • June 20, 2018

Published In

Start / End Page

  • 978 - 989

International Standard Serial Number (ISSN)

  • 0737-8017

International Standard Book Number 13 (ISBN-13)

  • 9781450355599

Digital Object Identifier (DOI)

  • 10.1145/3188745.3188966

Citation Source

  • Scopus