← Search

Assigning and Scheduling Generalized Malleable Jobs Under Subadditive or Submodular Processing Speeds

Dimitris Fotakis¹; Jannik Matuschke²; Orestis Papadigenopoulos³

¹ School of Electrical and Computer Engineering, National Technical University of Athens, 10682 Athens, Greece · ² Research Center for Operations Management, KU Leuven, 3000 Leuven, Belgium; · ³ Data Science Institute, Columbia University, New York, New York 10027

Handling Heterogeneous Machines in Malleable Scheduling Parallelization is an important and widespread technique to speed up the completion of time-critical tasks, not only in high-speed computing, but also in operations planning in production and logistics. A fundamental model in this context is that of malleable jobs, each of which can be assigned to a subset of machine for parallel processing. In “Assigning and Scheduling Generalized Malleable Jobs Under Submodular or Subadditive Processing Speeds,” Fotakis, Matuschke, and Papadigenopoulos go beyond the by now well-understood identical-machine setting in malleable scheduling and develop algorithmic approaches for scheduling malleable jobs under various discrete concavity assumptions on the joint processing speeds of the assigned (possibly very heterogeneous) machines. They show that under these assumptions, the task of finding a schedule of small makespan can be reduced to that of finding an assignment with small maximum machine load. For this latter problem, numerous efficient approximation algorithms are derived and their practical performance explored in a computational experiments. These results indicate that the computational challenges posed by parallelization in heterogeneous environments can indeed be overcome, enabling the optimization of heavily parallelized schedules in the aforementioned applications.

DOI

10.1287/opre.2022.0168

Volume

73 (3)

Pages

1598-1614

Language

en

Export

BibTeX

Sources

crossref openalex