A complete 4-parametric complexity classification of short shop scheduling problems

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

zbMATH Keywords

makespan minimizationshop schedulingcomplexity classification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

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

Related Items (8)

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

This page was built for publication: A complete 4-parametric complexity classification of short shop scheduling problems