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

DOI10.1080/10556788.2020.1734802MaRDI QIDQ5085264zbMATH OpenOpenAlexWikidataFDO

Authors I. D. Chernykh, Ekaterina Lgotina

Publication date 27 June 2022

Published in Optimization Methods \& 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)

Abstract: We consider two-machine routing open shop problem on a tree. In this problem a transportation network with a tree-like structure is given, and each node contains some jobs to be processed by two mobile machines. Machines are initially located in the predefined node called the depot, have to traverse the network to perform their operations on each job (and each job has to be processed by both machines in arbitrary order), and machines have to return to the depot after performing all the operations. The goal is to construct a feasible schedule for machines to process all the jobs and to return to the depot in shortest time possible. This problem is known to be NP-hard even in the case when the transportation network consists of just two nodes. We propose an instance reduction procedure which allows to transform any instance of the problem to a simplified instance on a chain with limited number of jobs. The reduction considered preserves the standard lower bound on the optimum. We describe four possible outcomes of this procedure and prove that in three of them the initial instance can be solved to the optimum in linear time, thus introducing a wide polynomially solvable subclass of the problem considered. Our research can be used as a foundation to construct efficient approximation algorithms for the two-machine routing open shop on a tree.

Recommendations

• Approximation algorithms for two-machine proportionate routing open shop on a tree
• Sufficient conditions of polynomial solvability of the two-machine preemptive routing open shop on a tree
• On the routing open shop problem with two machines on a two-vertex network
• A \(\frac 6 5\)-approximation algorithm for the two-machine routing open-shop problem on a two-node network
• A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing
• On a routing open shop problem on two nodes with unit processing times
• The 2-Machine Routing Open Shop on a Triangular Transportation Network
• Efficient approximation algorithms for the routing open shop problem
• The routing open-shop problem on a network: complexity and approximation
• The Routing Open Shop Problem: New Approximation Algorithms

Cites work

• scientific article; zbMATH DE number 3786125 (Why is no real title available?)
• A Simple Heuristic for m-Machine Flow-Shop and its Applications in Routing-Scheduling Problems
• A \(\frac 6 5\)-approximation algorithm for the two-machine routing open-shop problem on a two-node network
• A heuristic for the two-machine open-shop scheduling problem with transportation times
• An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times
• Completing partial schedules for open shop with unit processing times and routing
• Complexity results for flow-shop and open-shop scheduling problems with transportation delays
• On the routing open shop problem with two machines on a two-vertex network
• Open Shop Scheduling to Minimize Finish Time
• Routing Two-Machine Flowshop Problems on Networks with Special Structure
• Routing open shop with two nodes, unit processing times and equal number of jobs and machines
• Routing open shop with unrelated travel times
• Short Shop Schedules
• The 2-Machine Routing Open Shop on a Triangular Transportation Network
• The museum visitor routing problem
• The routing open-shop problem on a network: complexity and approximation
• Transporting jobs through a two‐machine open shop
• Two-machine shop scheduling problems with batch processing
• When difference in machine loads leads to efficient scheduling in open shops
• \(O(\log m)\)-approximation for the routing open shop problem

Cited in

(6)

• On the routing open shop problem with two machines on a two-vertex network
• Sufficient conditions of polynomial solvability of the two-machine preemptive routing open shop on a tree
• Approximation algorithms for two-machine proportionate routing open shop on a tree
• Two-machine routing open shop: How long is the optimal makespan?
• On the two-machine routing open shop on a tree with preemption allowed
• Irreducible bin packing and normality in routing open shop

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

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