Estimating the makespan of the two-valued restricted assignment problem

DOI10.4230/LIPICS.SWAT.2016.24MaRDI QIDQ5369526zbMATH OpenOpenAlexFDO

Authors K. Land, Marten Maack, Klaus Jansen

Publication date 17 October 2017

Full work available at URL http://dx.doi.org/10.4230/LIPIcs.SWAT.2016.24

zbMATH Keywords

estimation algorithmintegrality gaprestricted assignmentconfiguration LPunrelated scheduling

Mathematics Subject Classification ID

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

Recommendations

• Estimating the makespan of the two-valued restricted assignment problem
• On the configuration-LP of the restricted assignment problem
• On \((1,\varepsilon)\)-restricted assignment makespan minimization
• A quasi-polynomial approximation for the restricted assignment problem

Cited in

(8)

• Estimating the makespan of the two-valued restricted assignment problem
• Structured instances of restricted assignment with two processing times
• On the configuration-LP of the restricted assignment problem
• The 2-valued case of makespan minimization with assignment constraints
• Approximation algorithms for the graph balancing problem with two speeds and two job lengths
• Local search breaks 1.75 for graph balancing
• A quasi-polynomial approximation for the restricted assignment problem
• On minimizing the makespan when some jobs cannot be assigned on the same machine

This page was built for publication: Estimating the makespan of the two-valued restricted assignment problem

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