An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times

DOI10.33048/semi.2019.16.003zbMath1411.90161OpenAlexW3015742027MaRDI QIDQ2633586

René van Bevern, Artem V. Pyatkin, Sergey Sevast'janov

Publication date: 9 May 2019

Published in: Sibirskie Èlektronnye Matematicheskie Izvestiya (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.33048/semi.2019.16.003

zbMATH Keywords

schedulingroutingUETparameterized complexityFPT-algorithmOpen Shop problem

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (5)

Two-machine routing open shop on a tree: instance reduction and efficiently solvable subclass ⋮ On a routing Open Shop Problem on two nodes with unit processing times ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ Irreducible bin packing and normality in routing open shop ⋮ A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rural postman parameterized by the number of components of required edges
• Parameterized complexity of the \(k\)-arc Chinese postman problem
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• An application of simultaneous diophantine approximation in combinatorial optimization
• Parameterized complexity of machine scheduling: 15 open problems
• The parameterized approximability of TSP with deadlines
• A survey of scheduling problems with setup times or costs
• The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth
• Open Shop Scheduling to Minimize Finish Time
• Short Shop Schedules
• Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems
• A subexponential parameterized algorithm for Subset TSP on planar graphs
• Parameterized Algorithms
• Completing Partial Schedules for Open Shop with Unit Processing Times and Routing

This page was built for publication: An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times