Improved approximation algorithms for scheduling parallel jobs on identical clusters

DOI10.1016/J.TCS.2015.07.003MaRDI QIDQ496005zbMATH OpenOpenAlexFDO

Authors Marin Bougeret, Pierre-Francois Dutot, Denis Trystram, Klaus Jansen, Christina Robenek

Publication date 16 September 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.07.003

zbMATH Keywords

approximation algorithmschedulingstrip packingparallel job

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Recommendations

• Approximation algorithms for scheduling parallel jobs
• Approximation Algorithms for Scheduling Parallel Jobs: Breaking the Approximation Ratio of 2
• On-line scheduling of parallel jobs in heterogeneous multiple clusters
• Linear time algorithms for multiple cluster scheduling and multiple strip packing
• A New Approximation Algorithm for the Nonpreemptive Scheduling of Independent Jobs on Identical Parallel Processors

Cites work

• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
• Approximate algorithms to pack rectangles into several strips
• Approximating the non-contiguous multiple organization packing problem
• Bounds on Multiprocessing Timing Anomalies
• Evaluation of a MULTIFIT-based scheduling algorithm
• Improved approximation algorithms for scheduling parallel jobs on identical clusters
• On-Line Multiple-Strip Packing

Cited in

(10)

• Improved approximation algorithms for scheduling parallel jobs on identical clusters
• Algorithms for hierarchical and semi-partitioned parallel scheduling
• Improved algorithms to minimize workload balancing criteria on identical parallel machines
• Approximating the non-contiguous multiple organization packing problem
• Approximation algorithms for scheduling monotonic moldable tasks on multiple platforms
• Scheduling distributed clusters of parallel machines: primal-dual and LP-based approximation algorithms
• On-line scheduling of parallel jobs in heterogeneous multiple clusters
• Scheduling parallel jobs on heterogeneous platforms
• An improved LS algorithm for the problem of scheduling multi groups of jobs on multi processors at the same speed
• Linear time algorithms for multiple cluster scheduling and multiple strip packing

This page was built for publication: Improved approximation algorithms for scheduling parallel jobs on identical clusters

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