On the Approximability of Single-Machine Scheduling with Precedence Constraints
From MaRDI portal
Publication:2884295
DOI10.1287/moor.1110.0512zbMath1238.90059OpenAlexW2058023231MaRDI QIDQ2884295
Ola Svensson, Nikolaus Mutsanas, Monaldo Mastrolilli, Christoph Ambühl
Publication date: 24 May 2012
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.1110.0512
Analysis of algorithms and problem complexity (68Q25) Combinatorics of partially ordered sets (06A07) Deterministic scheduling theory in operations research (90B35) Coloring of graphs and hypergraphs (05C15) Approximation algorithms (68W25)
Related Items (10)
A survey on how the structure of precedence constraints may change the complexity class of scheduling problems ⋮ A \((2 + \epsilon)\)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective ⋮ On Submodular Search and Machine Scheduling ⋮ Scheduling results applicable to decision-theoretic troubleshooting ⋮ The feedback arc set problem with triangle inequality is a vertex cover problem ⋮ A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective ⋮ Online Linear Optimization for Job Scheduling Under Precedence Constraints ⋮ Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems ⋮ Decision diagrams for solving a job scheduling problem under precedence constraints ⋮ Approximability of scheduling problems with resource consuming jobs
This page was built for publication: On the Approximability of Single-Machine Scheduling with Precedence Constraints
