Generalized Malleable Scheduling via Discrete Concavity.

Abstract: In malleable scheduling, jobs can be executed simultaneously on multiple machines with the processing time depending on the number of allocated machines. Each job is required to be executed non-preemptively and in unison, i.e., it has to occupy the same time interval on all its allocated machines.

In this talk, we discuss a generalization of malleable scheduling, in which a function f(S, j) determines the processing time of job j on machine subset S. Under different discrete concavity assumptions on 1/f(S,j), we show that the scheduling problem can be approximated by a considerably simpler assignment problem and derive LP-based approximation algorithms.

We also highlight a connection to the problem of fairly allocating resources (the Santa Claus problem and its generalizations) and show how our results imply resource-augmented approximation algorithms for this setting.

Posted on Jul 5, 2021 in ACGO, Seminars