APPROXIMATION ALGORITHMS FOR SCHEDULING MALLEABLE TASKS UNDER PRECEDENCE CONSTRAINTS

DOI10.1142/S0129054102001308MaRDI QIDQ3021973zbMATH OpenOpenAlexFDO

Authors Renaud Lepère, Gerhard J. Woeginger, Denis Trystram

Publication date 22 June 2005

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054102001308

zbMATH Keywords

approximation algorithmparallel computingschedulingproject managementprecedence constraintsbounded widthmalleable tasksdiscrete time-cost tradeoff problemseries parallel order

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1875414
• A $\frac32$‐Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks
• An approximation algorithm for scheduling malleable tasks under general precedence constraints
• Algorithms and Computation
• Scheduling malleable tasks with precedence constraints

Cites work

• A decomposition theorem for partially ordered sets
• Approximation algorithms for the discrete time-cost tradeoff problem
• Complexity of Scheduling Parallel Task Systems
• Complexity of Scheduling under Precedence Constraints
• The discrete time-cost tradeoff problem revisited

Cited in

(14)

• A monotone approximation algorithm for scheduling with precedence constraints
• Algorithms for scheduling deadline-sensitive malleable tasks
• Algorithms and Computation
• scientific article; zbMATH DE number 2086932 (Why is no real title available?)
• Scheduling malleable tasks with precedence constraints
• Precedence-constrained scheduling of malleable jobs with preemption
• scientific article; zbMATH DE number 1875414 (Why is no real title available?)
• Approximate Deadline-Scheduling with Precedence Constraints
• Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width
• An approximation algorithm for scheduling trees of malleable tasks
• Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width
• Layer-based scheduling algorithms for multiprocessor-tasks with precedence constraints
• A \(\frac 54\)-approximation algorithm for scheduling identical malleable tasks
• A constant-factor approximation for generalized malleable scheduling under \(M^\natural \)-concave processing speeds

This page was built for publication: APPROXIMATION ALGORITHMS FOR SCHEDULING MALLEABLE TASKS UNDER PRECEDENCE CONSTRAINTS

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