A \((2 + \epsilon)\)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
From MaRDI portal
Publication:2417184
DOI10.1016/j.orl.2018.05.007OpenAlexW2962845733MaRDI QIDQ2417184
Publication date: 11 June 2019
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1706.07604
Related Items (5)
Approximation algorithms for some position-dependent scheduling problems ⋮ Approximation Algorithms for Generalized Path Scheduling ⋮ A new approximation algorithm for unrelated parallel machine scheduling with release dates ⋮ Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates ⋮ Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems
Cites Work
- Unnamed Item
- A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
- Structure of a simple scheduling polyhedron
- On the Approximability of Single-Machine Scheduling with Precedence Constraints
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
- A supermodular relaxation for scheduling with release dates
- Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds
- Optimal Long Code Test with One Free Bit
- Polynomial time approximation schemes for the traveling repairman and other minimum latency problems.
This page was built for publication: A \((2 + \epsilon)\)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
