Near-Optimal Solutions and Large Integrality Gaps for Almost All Instances of Single-Machine Precedence-Constrained Scheduling

DOI10.1287/moor.1100.0479zbMath1231.90213OpenAlexW2162099397MaRDI QIDQ3169127

Andreas S. Schulz, Nelson A. Uhan

Publication date: 27 April 2011

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/67660

zbMATH Keywords

schedulingprobabilistic analysisintegrality gaplinear orderingnear-optimal solution

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (3)

Precedence theorems and dynamic programming for the single-machine weighted tardiness problem ⋮ Integrated optimization of test case selection and sequencing for reliability testing of the mainboard of Internet backbone routers ⋮ An exact algorithm for the precedence-constrained single-machine scheduling problem

This page was built for publication: Near-Optimal Solutions and Large Integrality Gaps for Almost All Instances of Single-Machine Precedence-Constrained Scheduling