Improved approximation algorithms for scheduling parallel jobs on identical clusters

DOI10.1016/J.TCS.2015.07.003zbMATH Open1329.68284OpenAlexW784101583MaRDI QIDQ496005FDOQ496005

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

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

zbMATH Keywords

approximation algorithmschedulingstrip packingparallel job

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Approximation algorithms for scheduling monotonic moldable tasks on multiple platforms
• Linear Time Algorithms for Multiple Cluster Scheduling and Multiple Strip Packing
• Algorithms for hierarchical and semi-partitioned parallel scheduling
• Improved algorithms to minimize workload balancing criteria on identical parallel machines
• On-line scheduling of parallel jobs in heterogeneous multiple clusters
• Improved approximation algorithms for scheduling parallel jobs on identical clusters
• Approximating the non-contiguous multiple organization packing problem
• An improved LS algorithm for the problem of scheduling multi groups of jobs on multi processors at the same speed

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)