A $\frac32$‐Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks
From MaRDI portal
Publication:5386206
DOI10.1137/S0097539701385995zbMath1147.90007MaRDI QIDQ5386206
Grégory Mounié, Denis Trystram, Christophe Rapine
Publication date: 22 April 2008
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Approximation algorithms (68W25)
Related Items
Resource loading with time windows ⋮ A constant-factor approximation for generalized malleable scheduling under \(M^\natural \)-concave processing speeds ⋮ Machine scheduling with resource dependent processing times ⋮ Malleable scheduling beyond identical machines ⋮ An improved approximation algorithm for scheduling monotonic moldable tasks ⋮ Efficient approximation algorithms for scheduling moldable tasks ⋮ Scheduling malleable tasks with precedence constraints ⋮ Approximation algorithms for scheduling monotonic moldable tasks on multiple platforms ⋮ Scheduling personnel for the build-up of unit load devices at an air cargo terminal with limited space ⋮ Unnamed Item ⋮ Optimizing the stretch of independent tasks on a cluster: from sequential tasks to moldable tasks ⋮ An effective approximation algorithm for the malleable parallel task scheduling problem ⋮ Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width ⋮ Improved results for scheduling batched parallel jobs by using a generalized analysis framework ⋮ Bicriteria scheduling for contiguous and non contiguous parallel tasks ⋮ Competitive online scheduling of perfectly malleable jobs with setup times ⋮ A dominant class of schedules for malleable jobs in the problem to minimize the total weighted completion time ⋮ Closing the Gap for Pseudo-Polynomial Strip Packing ⋮ Online scheduling of moldable parallel tasks ⋮ Online scheduling of parallelizable jobs in the directed acyclic graphs and speed-up curves models
