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.003MaRDI QIDQ2633586zbMATH OpenOpenAlexFDO

Authors René van Bevern, Artem Pyatkin, Sergey Sevastyanov

Publication date 9 May 2019

Published in Sibirskie Elektronnye Matematicheskie Izvestiya (Search for Journal in Brave)

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

zbMATH Keywords

schedulingparameterized complexityroutingFPT-algorithmUETOpen Shop problem

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• Efficient approximation algorithms for the routing open shop problem
• The Routing Open Shop Problem: New Approximation Algorithms
• On a routing open shop problem on two nodes with unit processing times
• A Note On The Complexity Of Openshop Scheduling Problems
• Efficient algorithms for the routing open shop with unrelated travel times on cacti
• \(O(\log m)\)-approximation for the routing open shop problem
• The routing open-shop problem on a network: complexity and approximation
• A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing
• A branch \(\&\) bound algorithm for the open-shop problem
• A tabu search algorithm for the open shop scheduling problem

Cites work

• scientific article; zbMATH DE number 44978 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• A subexponential parameterized algorithm for subset TSP on planar graphs
• A survey of scheduling problems with setup times or costs
• An application of simultaneous diophantine approximation in combinatorial optimization
• Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems
• Completing partial schedules for open shop with unit processing times and routing
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• Open Shop Scheduling to Minimize Finish Time
• Parameterized algorithms
• Parameterized complexity of machine scheduling: 15 open problems
• Parameterized complexity of the \(k\)-arc Chinese postman problem
• Rural postman parameterized by the number of components of required edges
• Short Shop Schedules
• The complexity of arc routing problems
• The mixed Chinese postman problem parameterized by pathwidth and treedepth
• The parameterized approximability of TSP with deadlines

Cited in

(6)

• On a routing open shop problem on two nodes with unit processing times
• Two-machine routing open shop on a tree: instance reduction and efficiently solvable subclass
• The Routing Open Shop Problem: New Approximation Algorithms
• 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

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

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