Hardness of Precedence Constrained Scheduling on Identical Machines

DOI10.1137/100810502zbMath1252.68145OpenAlexW1995073517MaRDI QIDQ3115866

Ola Svensson

Publication date: 11 February 2012

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/100810502

zbMATH Keywords

schedulinghardness of approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

A survey on how the structure of precedence constraints may change the complexity class of scheduling problems ⋮ Towards Tight Lower Bounds for Scheduling Problems ⋮ Handling precedence constraints in scheduling problems by the sequence pair representation ⋮ Server cloud scheduling ⋮ An improved approximation algorithm for scheduling under arborescence precedence constraints ⋮ Approximate and robust bounded job start scheduling for Royal Mail delivery offices ⋮ Server cloud scheduling

This page was built for publication: Hardness of Precedence Constrained Scheduling on Identical Machines