Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations
From MaRDI portal
Publication:5117378
DOI10.1137/17M1156332zbMath1452.68277arXiv1707.08039OpenAlexW3016020363MaRDI QIDQ5117378
Publication date: 25 August 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1707.08039
Related Items
Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints, Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for scheduling unrelated parallel machines
- Efficient scheduling of tasks without full use of processor resources
- Minimizing average completion time in the presence of release dates
- Approximation algorithms for shop scheduling problems with minsum objective
- A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- Approximation Techniques for Average Completion Time Scheduling
- A PTAS for minimizing the weighted sum of job completion times on parallel machines
- Conditional hardness of precedence constrained scheduling on identical machines
- Minimizing Flow-Time on Unrelated Machines
- Convex quadratic and semidefinite programming relaxations in scheduling
- Towards Tight Lower Bounds for Scheduling Problems
- Approximation schemes for preemptive weighted flow time
- Minimizing Average Flow Time on Unrelated Machines
- Complexity of Scheduling under 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
- On the Configuration-LP of the Restricted Assignment Problem
- Scheduling Unrelated Machines by Randomized Rounding
- Santa Claus Schedules Jobs on Unrelated Machines
- Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
- Optimal Long Code Test with One Free Bit
- A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
- On (1,∊)-Restricted Assignment Makespan Minimization
- Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems
- Bounds on Multiprocessing Timing Anomalies
