An effective approximation algorithm for the malleable parallel task scheduling problem

DOI10.1016/j.jpdc.2012.01.011zbMath1242.68035OpenAlexW2042999105MaRDI QIDQ433456

Fa Zhang, Gongming Wang, Liya Fan, 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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scheduling malleable tasks on parallel processors to minimize the makespan
• List scheduling of parallel tasks
• A 2.5 times optimal algorithm for packing in two dimensions
• Dynamic scheduling on parallel machines
• Linear-Time approximation schemes for scheduling malleable parallel tasks
• Computing optimal preemptive schedules for parallel tasks: linear programming approaches
• Two-dimensional packing problems: a survey
• Scheduling malleable parallel tasks: an asymptotic fully polynomial time approximation scheme
• Competitive online scheduling of perfectly malleable jobs with setup times
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• Approximation Algorithms for Scheduling Parallel Jobs: Breaking the Approximation Ratio of 2
• Scheduling Multiprocessor Tasks to Minimize Schedule Length
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Orthogonal Packings in Two Dimensions
• Project Scheduling with Continuously-Divisible, Doubly Constrained Resources
• A Heuristic of Scheduling Parallel Tasks and Its Analysis
• Bounds for Multiprocessor Scheduling with Resource Constraints
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• A $\frac32$‐Approximation Algorithm for Scheduling Independent Monotonic Malleable Tasks
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Scheduling independent multiprocessor tasks

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