Approximation algorithms for the graph balancing problem with two speeds and two job lengths

DOI10.1007/s10878-018-0339-xzbMath1423.90096OpenAlexW2886895431WikidataQ129364370 ScholiaQ129364370MaRDI QIDQ2424664

Daniel R. Page, Roberto Solis-Oba

Publication date: 25 June 2019

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-018-0339-x

zbMATH Keywords

scheduling theoryunrelated parallel machinesmakespan minimizationapproximation algorithmsgraph balancing problemrestricted assignment problem

Mathematics Subject Classification ID

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

Related Items (1)

Makespan minimization on unrelated parallel machines with a few bags

Cites Work

• Unnamed Item
• On the configuration-LP for scheduling on unrelated machines
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• Approximation algorithms for scheduling unrelated parallel machines
• An approximation algorithm for the generalized assignment problem
• Parallel machine scheduling of machine-dependent jobs with unit-length.
• A 3/2-approximation algorithm for the graph balancing problem with two weights
• The 2-valued case of makespan minimization with assignment constraints
• A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
• A quasi-polynomial approximation for the restricted assignment problem
• Graph balancing: a special case of scheduling unrelated parallel machines
• An optimal rounding gives a better approximation for scheduling unrelated machines
• On some special cases of the restricted assignment problem
• The Design of Approximation Algorithms
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• On the Configuration-LP of the Restricted Assignment Problem
• A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges
• Santa Claus Schedules Jobs on Unrelated Machines
• On (1,∊)-Restricted Assignment Makespan Minimization
• Estimating The Makespan of The Two-Valued Restricted Assignment Problem

This page was built for publication: Approximation algorithms for the graph balancing problem with two speeds and two job lengths