A complete 4-parametric complexity classification of short shop scheduling problems
From MaRDI portal
Publication:2434295
DOI10.1007/s10951-011-0243-zzbMath1280.90057OpenAlexW1987322775MaRDI QIDQ2434295
Sergey Sevast'janov, Alexander V. Kononov, M. I. Sviridenko
Publication date: 5 February 2014
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10951-011-0243-z
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)
Related Items
A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job ⋮ Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches ⋮ A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack ⋮ A 5-parameter complexity classification of the two-stage flow shop scheduling problem with job dependent storage requirements ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ On some properties of optimal schedules in the job shop problem with preemption and an arbitrary regular criterion ⋮ Scheduling meets \(n\)-fold integer programming
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Properties of optimal schedules in preemptive shop scheduling
- Approximation algorithms for scheduling unrelated parallel machines
- Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
- The mixed shop scheduling problem
- Three, four, five, six, or the complexity of scheduling with communication delays
- Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
- An introduction to multi-parameter complexity analysis of discrete problems
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A polynomial algorithm for the three-machine open shop with a bottleneck machine
- Complexity of mixed shop scheduling problems: A survey
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- An Algorithm for Solving the Job-Shop Problem
- A Note on Open Shop Preemptive Schedules
- Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
- Open Shop Scheduling to Minimize Finish Time
- Complexity of Scheduling under Precedence Constraints
- The edge chromatic number of a directed/mixed multigraph
- Short Shop Schedules
- Closure properties of constraints
- Minimizing Makespan in No-Wait Job Shops
- The complexity of satisfiability problems
