Estimating the makespan of the two-valued restricted assignment problem

DOI10.4230/LIPICS.SWAT.2016.24zbMATH Open1378.90049OpenAlexW2573293934MaRDI QIDQ5369526FDOQ5369526

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

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

zbMATH Keywords

estimation algorithmintegrality gaprestricted assignmentconfiguration LPunrelated scheduling

Mathematics Subject Classification ID

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

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)