On the complexity of scheduling unrelated parallel machines with limited preemptions

DOI10.1016/j.orl.2023.02.004zbMath1525.90209OpenAlexW4319873307MaRDI QIDQ6161912

Jan Karel Lenstra, Nodari Vakhania

Publication date: 28 June 2023

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2023.02.004

zbMATH Keywords

schedulingunrelated parallel machinesNP-hardnesspreemption

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• On the geometry, preemptions and complexity of multiprocessor and shop scheduling
• Linear programming is log-space hard for P
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Scheduling with Deadlines and Loss Functions
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Parallel Scheduling Algorithms
• Optimal Preemptive Scheduling of Two Unrelated Processors
• Open Shop Scheduling to Minimize Finish Time
• Preemptive Scheduling of Uniform Processor Systems
• `` Strong NP-Completeness Results
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Reducibility among Combinatorial Problems

This page was built for publication: On the complexity of scheduling unrelated parallel machines with limited preemptions