A supermodular relaxation for scheduling with release dates
From MaRDI portal
Publication:4645930
DOI10.1007/3-540-61310-2_22zbMath1414.90149OpenAlexW1621441552MaRDI QIDQ4645930
Publication date: 11 January 2019
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-61310-2_22
Related Items
A \((2 + \epsilon)\)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective ⋮ Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling ⋮ An improved greedy algorithm for stochastic online scheduling on unrelated machines ⋮ Randomized mechanism design for decentralized network scheduling ⋮ Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds ⋮ A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective ⋮ Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms ⋮ On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems ⋮ Hybrid Flow Shop Scheduling: Heuristic Solutions and LP-Based Lower Bounds ⋮ A 1. 47-approximation for a preemptive single-machine scheduling problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Formulating the single machine sequencing problem with release dates as a mixed integer program
- Submodular functions and optimization
- Structure of a simple scheduling polyhedron
- A Sequencing Problem with Release Dates and Clustered Jobs
- An analysis of approximations for maximizing submodular set functions—I
- Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds
- Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds
