A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

DOI10.1016/j.orl.2016.07.016zbMath1408.90140arXiv1603.04690OpenAlexW2963832601MaRDI QIDQ1755846

Martin Skutella

Publication date: 11 January 2019

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1603.04690

zbMATH Keywords

machine schedulingapproximation algorithmprecedence constraintstotal weighted completion timeLP relaxation

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items

Unnamed Item, A \((2 + \epsilon)\)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective, An improved greedy algorithm for stochastic online scheduling on unrelated machines, Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations, A new approximation algorithm for unrelated parallel machine scheduling with release dates, An improved approximation algorithm for scheduling under arborescence precedence constraints, Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Single machine precedence constrained scheduling is a Vertex cover problem
• Minimizing average completion time in the presence of release dates
• Structure of a simple scheduling polyhedron
• Approximation Techniques for Average Completion Time Scheduling
• Single Machine Scheduling with Release Dates
• 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
• Single-Machine Scheduling with Precedence Constraints
• List Scheduling in Order of α-Points on a Single Machine