Strong LP formulations for scheduling splittable jobs on unrelated machines
From MaRDI portal
Publication:896269
DOI10.1007/s10107-014-0831-8zbMath1327.90067OpenAlexW2164915638WikidataQ65553897 ScholiaQ65553897MaRDI QIDQ896269
Ola Svensson, José Verschae, Leen Stougie, José R. Correa, Víctor Verdugo, Alberto Marchetti-Spaccamela, Jannik Matuschke
Publication date: 9 December 2015
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://ir.cwi.nl/pub/23272
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)
Related Items (9)
A constant-factor approximation for generalized malleable scheduling under \(M^\natural \)-concave processing speeds ⋮ Malleable scheduling beyond identical machines ⋮ A branch‐and‐price algorithm for identical parallel machine scheduling with multiple milestones ⋮ Splitting versus setup trade-offs for scheduling to minimize weighted completion time ⋮ Unnamed Item ⋮ Scheduling cleaning activities on trains by minimizing idle times ⋮ Approximating Weighted Completion Time for Order Scheduling with Setup Times ⋮ Unnamed Item ⋮ Empowering the configuration-IP: new PTAS results for scheduling with setup times
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the configuration-LP for scheduling on unrelated machines
- Approximation algorithms for scheduling unrelated parallel machines
- Lot-sizing scheduling with batch setup times
- Geometric algorithms and combinatorial optimization
- Parallel machine scheduling with splitting jobs
- Splitting versus setup trade-offs for scheduling to minimize weighted completion time
- Split scheduling with uniform setup times
- Graph balancing: a special case of scheduling unrelated parallel machines
- Minimizing total completion time subject to job release dates and preemption penalties
- A survey of scheduling problems with setup times or costs
- Quasi-polynomial Local Search for Restricted Max-Min Fair Allocation
- The Santa Claus problem
- The Design of Approximation Algorithms
- A threshold of ln n for approximating set cover
- Santa claus meets hypergraph matchings
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Integrating Scheduling with Batching and Lot-Sizing: A Review of Algorithms and Complexity
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Santa Claus Schedules Jobs on Unrelated Machines
- Approximating the Configuration-LP for Minimizing Weighted Sum of Completion Times on Unrelated Machines
- New Constructive Aspects of the Lovász Local Lemma
- Scheduling Jobs on Several Machines with the Job Splitting Property
This page was built for publication: Strong LP formulations for scheduling splittable jobs on unrelated machines
