Malleable scheduling beyond identical machines

DOI10.1007/S10951-022-00733-XMaRDI QIDQ6090217zbMATH OpenOpenAlexFDO

Authors Dimitris Fotakis, Jannik Matuschke, Orestis Papadigenopoulos

Publication date 14 November 2023

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/11232/

zbMATH Keywords

approximationschedulingmakespanpackingrestrictedroundinguniformparallelmachinesunrelatedjobsmalleablemoldable

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• A constant-factor approximation for generalized malleable scheduling under \(M^\natural \)-concave processing speeds
• Online malleable job scheduling for \(m\leq 3\)
• scientific article; zbMATH DE number 1003247
• Improved upper bounds for online malleable job scheduling
• Precedence-constrained scheduling of malleable jobs with preemption

Cites work

• scientific article; zbMATH DE number 1097351 (Why is no real title available?)
• scientific article; zbMATH DE number 2109192 (Why is no real title available?)
• A $\frac32$‐Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks
• An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays
• An approximation algorithm for scheduling malleable tasks under general precedence constraints
• Approximation algorithms for scheduling parallel jobs
• Approximation algorithms for scheduling unrelated parallel machines
• Bounds for Multiprocessor Scheduling with Resource Constraints
• Bounds on Multiprocessing Timing Anomalies
• Complexity of Scheduling Parallel Task Systems
• Linear-Time approximation schemes for scheduling malleable parallel tasks
• Precedence-constrained scheduling of malleable jobs with preemption
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Strong LP formulations for scheduling splittable jobs on unrelated machines
• The Parallel Evaluation of General Arithmetic Expressions
• Towards an Architecture-Independent Analysis of Parallel Algorithms
• UET scheduling with unit interprocessor communication delays
• Zero knowledge and the chromatic number

Cited in

(1)

• Malleable scheduling for flows of jobs and applications to MapReduce

This page was built for publication: Malleable scheduling beyond identical machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6090217)