Two-machine routing open shop on a tree: instance reduction and efficiently solvable subclass

DOI10.1080/10556788.2020.1734802zbMath1492.90054arXiv1911.00236OpenAlexW3098577567WikidataQ115005274 ScholiaQ115005274MaRDI QIDQ5085264

Ekaterina Lgotina, I. D. Chernykh

Publication date: 27 June 2022

Published in: Optimization Methods and Software (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1911.00236

zbMATH Keywords

schedulinginstance reductionrouting open shopoverloaded edgeoverloaded nodepolynomially solvable subclassstandard lower boundopen shop with delays

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (3)

Approximation algorithms for two-machine proportionate routing open shop on a tree ⋮ Irreducible bin packing and normality in routing open shop ⋮ Two-machine routing open shop: How long is the optimal makespan?

Cites Work

• Unnamed Item
• Complexity results for flow-shop and open-shop scheduling problems with transportation delays
• The museum visitor routing problem
• A heuristic for the two-machine open-shop scheduling problem with transportation times
• A \(\frac 6 5\)-approximation algorithm for the two-machine routing open-shop problem on a two-node network
• Two-machine shop scheduling problems with batch processing
• When difference in machine loads leads to efficient scheduling in open shops
• Routing open shop with two nodes, unit processing times and equal number of jobs and machines
• The routing open-shop problem on a network: complexity and approximation
• An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times
• Routing Open Shop with Unrelated Travel Times
• The 2-Machine Routing Open Shop on a Triangular Transportation Network
• Transporting jobs through a two‐machine open shop
• Open Shop Scheduling to Minimize Finish Time
• Routing Two-Machine Flowshop Problems on Networks with Special Structure
• Short Shop Schedules
• A Simple Heuristic for m-Machine Flow-Shop and its Applications in Routing-Scheduling Problems
• O(log m)-approximation for the routing open shop problem
• On the routing open shop problem with two machines on a two-vertex network
• Completing Partial Schedules for Open Shop with Unit Processing Times and Routing

This page was built for publication: Two-machine routing open shop on a tree: instance reduction and efficiently solvable subclass