Load Balancing Algorithms on Scheduling Problems with a Concave Function of the Load.

Abstract: 

In load balancing scheduling problems n jobs are to be assigned to m machines. Each job has its own processing time, and we define the load of a machine as the sum of the processing time of all jobs assigned to it.

In this work, the machines have a concave non-decreasing function (accessed through a value oracle) applied to their loads and our goal is to maximize the sum of these valuations.

This setting models a productivity maximization of machines where we aim to allocate indivisible resources, such as fuel tanks.

We prove the existence of a PTAS for the offline version, which is the best possible as the underlying decision problem is strongly NP-hard.

We also explore the online version, where jobs arrive one by one revealing their processing time and must be allocated immediately. We first show that the List Scheduling greedy algorithm is 3/4-competitive in adversarial order. Additionally, we provide an upper bound of ≈ 0.809 (ϕ/2 where ϕ is the golden ratio) for the competitive ratio of any algorithm in this context. For the special case of only two machines, we present an algorithm that matches the given upper bound.

This is joint work with José Soto.

Posted on Sep 25, 2023 in ACGO, Seminars