Complete Complexity Classification of Short Shop Scheduling

DOI10.1007/978-3-642-03351-3_22MaRDI QIDQ3392957zbMATH OpenOpenAlexFDO

Authors Alexander Kononov, Maxim Sviridenko, Sergey Sevastyanov

Publication date 18 August 2009

Published in Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03351-3_22

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A complete 4-parametric complexity classification of short shop scheduling problems
• On scheduling cycle shops: Classification, complexity and approximation
• Complexity of a class of task scheduling problems
• The complexity of cyclic shop scheduling problems
• Combinations of some shop scheduling problems and the shortest path problem: complexity and approximation algorithms
• Complexity of mixed shop scheduling problems: A survey
• Complexity of shop-scheduling problems with fixed number of jobs: a survey
• scientific article; zbMATH DE number 3860868
• On the computational complexity of (maximum) shift class scheduling
• Scheduling problem: complexity analysis and polynomially solvable subclasses

Cites work

• Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
• An Algorithm for Solving the Job-Shop Problem
• Approximation algorithms for scheduling unrelated parallel machines
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity of mixed shop scheduling problems: A survey
• Complexity of Scheduling under Precedence Constraints
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• scientific article; zbMATH DE number 1302193 (Why is no real title available?)
• Minimizing Makespan in No-Wait Job Shops
• Open Shop Scheduling to Minimize Finish Time
• Short Shop Schedules
• The edge chromatic number of a directed/mixed multigraph
• Three, four, five, six, or the complexity of scheduling with communication delays

Cited in

(3)

• Complexity of mixed shop scheduling problems: A survey
• A complete 4-parametric complexity classification of short shop scheduling problems
• Four-parametric complexity analysis for an open shop problem

This page was built for publication: Complete Complexity Classification of Short Shop Scheduling

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