Strong LP formulations for scheduling splittable jobs on unrelated machines

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

Mathematics Subject Classification ID

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