Malleable scheduling beyond identical machines

Dimitris Fotakis (), Jannik Matuschke () and Orestis Papadigenopoulos ()
Additional contact information
Dimitris Fotakis: National Technical University of Athens
Jannik Matuschke: KU Leuven
Orestis Papadigenopoulos: The University of Texas at Austin

Journal of Scheduling, 2023, vol. 26, issue 5, No 3, 425-442

Abstract: Abstract In malleable job scheduling, jobs can be executed simultaneously on multiple machines with the processing time depending on the number of allocated machines. In this setting, jobs are required to be executed non-preemptively and in unison, in the sense that they occupy, during their execution, the same time interval over all the machines of the allocated set. In this work, we study generalizations of malleable job scheduling inspired by standard scheduling on unrelated machines. Specifically, we introduce a general model of malleable job scheduling, where each machine has a (possibly different) speed for each job, and the processing time of a job j on a set of allocated machines S depends on the total speed of S with respect to j. For machines with unrelated speeds, we show that the optimal makespan cannot be approximated within a factor less than $$\frac{e}{e-1}$$ e e - 1 , unless $$P = NP$$ P = N P . On the positive side, we present polynomial-time algorithms with approximation ratios $$\frac{2e}{e-1}$$ 2 e e - 1 for machines with unrelated speeds, 3 for machines with uniform speeds, and 7/3 for restricted assignments on identical machines. Our algorithms are based on deterministic LP rounding. They result in sparse schedules, in the sense that each machine shares at most one job with other machines. We also prove lower bounds on the integrality gap of $$1+\varphi $$ 1 + φ for unrelated speeds ( $$\varphi $$ φ is the golden ratio) and 2 for uniform speeds and restricted assignments. To indicate the generality of our approach, we show that it also yields constant factor approximation algorithms for a variant where we determine the effective speed of a set of allocated machines based on the $$L_p$$ L p norm of their speeds.

Keywords: Malleable; Scheduling; Packing; Jobs; Machines; Parallel; Makespan; Unrelated; Uniform; Restricted; Moldable; Rounding; Approximation (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-022-00733-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:26:y:2023:i:5:d:10.1007_s10951-022-00733-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-022-00733-x

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().