Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds
From MaRDI portal
Publication:4645931
DOI10.1007/3-540-61310-2_23zbMath1414.90167OpenAlexW1960330418MaRDI QIDQ4645931
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_23
Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)
Related Items (19)
Single machine scheduling problems with uncertain parameters and the OWA criterion ⋮ A General Framework for Approximating Min Sum Ordering Problems ⋮ Minimizing the sum of weighted completion times in a concurrent open shop ⋮ 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 ⋮ Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games ⋮ Static Routing in Stochastic Scheduling: Performance Guarantees and Asymptotic Optimality ⋮ Randomized mechanism design for decentralized network scheduling ⋮ Approximating Single Machine Scheduling with Scenarios ⋮ A supermodular relaxation for scheduling with release dates ⋮ Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds ⋮ An integer programming approach to optimal basic block instruction scheduling for single-issue processors ⋮ A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective ⋮ A note on weighted completion time minimization in a flexible flow shop ⋮ Risk-averse single machine scheduling: complexity and approximation ⋮ Order Scheduling Models: Hardness and Algorithms ⋮ Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates ⋮ Hybrid Flow Shop Scheduling: Heuristic Solutions and LP-Based Lower Bounds ⋮ Decision diagrams for solving a job scheduling problem under precedence constraints
Cites Work
- Approximation algorithms for scheduling unrelated parallel machines
- Formulating the single machine sequencing problem with release dates as a mixed integer program
- A multi-stage parallel-processor flowshop problem with minimum flowtime
- Geometric algorithms and combinatorial optimization
- An approximation algorithm for the generalized assignment problem
- Structure of a simple scheduling polyhedron
- Lower Bounds for the Head-Body-Tail Problem on Parallel Machines: A Computational Study of the Multiprocessor Flow Shop
- Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
- Flowshop and Jobshop Schedules: Complexity and Approximation
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
- The Complexity of Flowshop and Jobshop Scheduling
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Scheduling jobs with communication delays: Using infeasible solutions for approximation
- A supermodular relaxation for scheduling with release dates
- Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds
- Scheduling independent tasks to reduce mean finishing time
- Scheduling jobs that arrive over time
- Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds
