Improved approximation algorithms for scheduling parallel jobs on identical clusters

DOI10.1016/j.tcs.2015.07.003zbMath1329.68284OpenAlexW784101583MaRDI QIDQ496005

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

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

schedulingapproximation algorithmstrip packingparallel job

Mathematics Subject Classification ID

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

Related Items (4)

Approximation algorithms for scheduling monotonic moldable tasks on multiple platforms ⋮ Linear Time Algorithms for Multiple Cluster Scheduling and Multiple Strip Packing ⋮ Improved approximation algorithms for scheduling parallel jobs on identical clusters ⋮ Algorithms for hierarchical and semi-partitioned parallel scheduling

Cites Work

• Improved approximation algorithms for scheduling parallel jobs on identical clusters
• 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
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• Approximate algorithms to pack rectangles into several strips
• Bounds on Multiprocessing Timing Anomalies

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