Approximation algorithms for two-machine proportionate routing open shop on a tree

DOI10.1007/978-3-031-35305-5_13zbMATH Open1520.90098OpenAlexW4381956460MaRDI QIDQ6134059FDOQ6134059

Ilya Chernykh, Olga Krivonogova, Anna Shmyrina

Publication date: 21 August 2023

Published in: Mathematical Optimization Theory and Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-35305-5_13

Recommendations

• Two-machine routing open shop on a tree: instance reduction and efficiently solvable subclass
• A \(\frac 6 5\)-approximation algorithm for the two-machine routing open-shop problem on a two-node network
• On the routing open shop problem with two machines on a two-vertex network
• Efficient approximation algorithms for the routing open shop problem
• Sufficient conditions of polynomial solvability of the two-machine preemptive routing open shop on a tree
• The Routing Open Shop Problem: New Approximation Algorithms
• On a routing open shop problem on two nodes with unit processing times
• \(O(\log m)\)-approximation for the routing open shop problem
• The routing open-shop problem on a network: complexity and approximation
• A 3/2 algorithm for two-machine open shop with route-dependent processing times

zbMATH Keywords

approximation algorithmsrouting open shopoptima localizationunrelated travel timesproportionate open shop

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Open Shop Scheduling to Minimize Finish Time
• Short Shop Schedules
• Scheduling ordered open shops
• Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop
• A \(\frac 6 5\)-approximation algorithm for the two-machine routing open-shop problem on a two-node network
• The routing open-shop problem on a network: complexity and approximation
• A cyclical search for the two machine flow shop and open shop to minimise finishing time
• Title not available (Why is that?)
• Polynomial time approximation algorithms for proportionate open‐shop scheduling
• A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing
• Efficient algorithms for the routing open shop with unrelated travel times on cacti
• Some positive news on the proportionate open shop problem
• Routing Open Shop with Unrelated Travel Times
• Two-machine routing open shop: How long is the optimal makespan?
• The 2-Machine Routing Open Shop on a Triangular Transportation Network
• Two-machine routing open shop on a tree: instance reduction and efficiently solvable subclass
• How the difference in travel times affects the optima localization for the routing open shop
• Irreducible bin packing and normality in routing open shop

Cited In (5)

• The Routing Open Shop Problem: New Approximation Algorithms
• On the routing open shop problem with two machines on a two-vertex network
• The 2-Machine Routing Open Shop on a Triangular Transportation Network
• A \(\frac 6 5\)-approximation algorithm for the two-machine routing open-shop problem on a two-node network
• Two-machine routing open shop on a tree: instance reduction and efficiently solvable subclass

This page was built for publication: Approximation algorithms for two-machine proportionate routing open shop on a tree

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