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.90167MaRDI 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
90B35: Deterministic scheduling theory in operations research
90C59: Approximation methods and heuristics in mathematical programming
Related Items
A supermodular relaxation for scheduling with release dates, Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds, A General Framework for Approximating Min Sum Ordering Problems, 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, Hybrid Flow Shop Scheduling: Heuristic Solutions and LP-Based Lower Bounds, Decision diagrams for solving a job scheduling problem under precedence constraints, Order Scheduling Models: Hardness and Algorithms, A note on weighted completion time minimization in a flexible flow shop, Single machine scheduling problems with uncertain parameters and the OWA criterion, Minimizing the sum of weighted completion times in a concurrent open shop, 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, Risk-averse single machine scheduling: complexity and approximation, Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates, A \((2 + \epsilon)\)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective, Approximating Single Machine Scheduling with Scenarios
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
