APPROXIMATION ALGORITHMS FOR SCHEDULING MALLEABLE TASKS UNDER PRECEDENCE CONSTRAINTS

DOI10.1142/S0129054102001308zbMATH Open1066.68010OpenAlexW1975231449MaRDI QIDQ3021973FDOQ3021973

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

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

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)

Cites Work

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

Cited In (14)

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

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)