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

DOI10.1007/978-3-031-35305-5_13MaRDI QIDQ6134059zbMATH OpenOpenAlexFDO

Authors 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

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)

Recommendations

• Two-machine routing open shop on a tree: instance reduction and efficiently solvable subclass
• A 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

Cites work

• scientific article; zbMATH DE number 3786125 (Why is no real title available?)
• scientific article; zbMATH DE number 44978 (Why is no real title available?)
• scientific article; zbMATH DE number 3503127 (Why is no real title available?)
• A 6 5-approximation algorithm for the two-machine routing open-shop problem on a two-node network
• A cyclical search for the two machine flow shop and open shop to minimise finishing time
• 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
• How the difference in travel times affects the optima localization for the routing open shop
• Irreducible bin packing and normality in routing open shop
• Open Shop Scheduling to Minimize Finish Time
• Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop
• Polynomial time approximation algorithms for proportionate open-shop scheduling
• Routing open shop with unrelated travel times
• Scheduling ordered open shops
• Short Shop Schedules
• Some positive news on the proportionate open shop problem
• The 2-Machine Routing Open Shop on a Triangular Transportation Network
• The routing open-shop problem on a network: complexity and approximation
• Two-machine routing open shop on a tree: instance reduction and efficiently solvable subclass
• Two-machine routing open shop: How long is the optimal makespan?

Cited in

(7)

• 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 6 5-approximation algorithm for the two-machine routing open-shop problem on a two-node network
• How the difference in travel times affects the optima localization for the routing open shop
• On complexity of two-machine routing propotionate open shop
• 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)