An effective approximation algorithm for the malleable parallel task scheduling problem

DOI10.1016/J.JPDC.2012.01.011MaRDI QIDQ433456zbMATH OpenOpenAlexFDO

Authors Liya Fan, Fa Zhang, Gongming Wang, Zhi-Yong Liu

Publication date 13 July 2012

Published in Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jpdc.2012.01.011

zbMATH Keywords

approximation algorithmparallel computingscheduling algorithm

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25) Parallel algorithms in computer science (68W10)

Recommendations

• scientific article; zbMATH DE number 1003247
• Scheduling malleable tasks on parallel processors to minimize the makespan
• scientific article; zbMATH DE number 1863269
• A \frac32‐Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks
• An approximation algorithm for scheduling trees of malleable tasks

Cites work

• scientific article; zbMATH DE number 1271325 (Why is no real title available?)
• scientific article; zbMATH DE number 1003247 (Why is no real title available?)
• scientific article; zbMATH DE number 3805259 (Why is no real title available?)
• scientific article; zbMATH DE number 1863269 (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
• A 2.5 times optimal algorithm for packing in two dimensions
• A Heuristic of Scheduling Parallel Tasks and Its Analysis
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• A near-optimal solution to a two-dimensional cutting stock problem
• Approximation Algorithms for Scheduling Parallel Jobs: Breaking the Approximation Ratio of 2
• Bounds for Certain Multiprocessing Anomalies
• Bounds for Multiprocessor Scheduling with Resource Constraints
• Bounds on Multiprocessing Timing Anomalies
• Competitive online scheduling of perfectly malleable jobs with setup times
• Computing optimal preemptive schedules for parallel tasks: linear programming approaches
• Dynamic scheduling on parallel machines
• Linear-Time approximation schemes for scheduling malleable parallel tasks
• List scheduling of parallel tasks
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Orthogonal Packings in Two Dimensions
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Project Scheduling with Continuously-Divisible, Doubly Constrained Resources
• Scheduling Multiprocessor Tasks to Minimize Schedule Length
• Scheduling independent multiprocessor tasks
• Scheduling malleable parallel tasks: an asymptotic fully polynomial time approximation scheme
• Scheduling malleable tasks on parallel processors to minimize the makespan
• Two-dimensional packing problems: a survey

Cited in

(2)

• Optimizing the stretch of independent tasks on a cluster: from sequential tasks to moldable tasks
• A \(\frac 54\)-approximation algorithm for scheduling identical malleable tasks

This page was built for publication: An effective approximation algorithm for the malleable parallel task scheduling problem

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