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

• 成果类型: Article
• 署名作者: Fotakis, Dimitris; Matuschke, Jannik; Papadigenopoulos, Orestis
• 署名单位: National Technical University of Athens; KU Leuven; Columbia University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0168
• 发表日期: 2025
• 关键词: malleable scheduling; makespan minimization; Approximation algorithms; (fractional) subadditivity; Submodularity; matroids

摘要

Malleable scheduling is a model that captures the possibility of parallelization to expedite the completion of time-critical tasks. A malleable job can be allocated and processed simultaneously on multiple machines, occupying the same time interval on all these machines. We study a general version of this setting, in which the functions determining the joint processing speed of machines for a given job follow different discrete concavity assumptions (subadditivity, fractional subadditivity, submodularity, and matroid ranks). We show that under these assumptions, the problem of scheduling malleable jobs at minimum makespan can be approximated by a considerably simpler assignment problem. Moreover, we provide efficient approximation algorithms for both the scheduling and the assignment problem, with increasingly stronger guarantees for increasingly stronger concavity assumptions, including a logarithmic approximation factor for the case of submodular processing speeds and a constant approximation factor when processing speeds are determined by matroid rank functions. Computational experiments indicate that our algorithms outperform the theoretical worst-case guarantees.