On the configuration-LP for scheduling on unrelated machines

DOI10.1007/S10951-013-0359-4MaRDI QIDQ490331zbMATH OpenOpenAlexFDO

Authors José Verschae, Andreas Wiese

Publication date 22 January 2015

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10951-013-0359-4

zbMATH Keywords

approximation algorithmsintegrality gapmachine schedulingconfiguration-LP

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Recommendations

• On the Configuration-LP for Scheduling on Unrelated Machines
• On the configuration-LP of the restricted assignment problem
• Strong LP formulations for scheduling splittable jobs on unrelated machines
• Graph balancing: a special case of scheduling unrelated parallel machines
• Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines

Cites work

• scientific article; zbMATH DE number 5764783 (Why is no real title available?)
• scientific article; zbMATH DE number 5764883 (Why is no real title available?)
• A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
• A note on graph balancing problems with restrictions
• An approximation algorithm for max-min fair allocation of indivisible goods
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Approximation algorithms for scheduling unrelated parallel machines
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• MaxMin allocation via degree lower-bounded arborescences
• New constructive aspects of the Lovász local lemma
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• On allocating goods to maximize fairness
• On the Configuration-LP for Scheduling on Unrelated Machines
• Parallel machine scheduling of machine-dependent jobs with unit-length.
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• Santa Claus Meets Hypergraph Matchings
• Santa claus meets hypergraph matchings
• The Santa Claus problem
• The power of preemption on unrelated machines and applications to scheduling orders

Cited in

(21)

• A 3/2-approximation algorithm for the graph balancing problem with two weights
• Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
• Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments
• Compact LP relaxations for allocation problems
• On the Configuration-LP for Scheduling on Unrelated Machines
• Graph balancing with orientation costs
• On the configuration-LP of the restricted assignment problem
• Optimal matroid partitioning problems
• Parameterized orientable deletion
• Optimal matroid partitioning problems
• Parameterized orientable deletion
• Strong LP Formulations for Scheduling Splittable Jobs on Unrelated Machines
• Strong LP formulations for scheduling splittable jobs on unrelated machines
• Greedy is optimal for online restricted assignment and smart grid scheduling for unit size jobs
• Semidefinite and linear programming integrality gaps for scheduling identical machines
• Approximation algorithms for the graph balancing problem with two speeds and two job lengths
• Semidefinite and linear programming integrality gaps for scheduling identical machines
• Approximating the configuration-LP for minimizing weighted sum of completion times on unrelated machines
• Better trees for Santa Claus
• Local search breaks 1.75 for graph balancing
• On minimizing the makespan when some jobs cannot be assigned on the same machine

This page was built for publication: On the configuration-LP for scheduling on unrelated machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490331)