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

DOI10.1080/10556788.2020.1734802zbMATH Open1492.90054arXiv1911.00236OpenAlexW3098577567WikidataQ115005274 ScholiaQ115005274MaRDI QIDQ5085264FDOQ5085264

Authors: I. D. Chernykh, Ekaterina Lgotina 

Publication date: 27 June 2022

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

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.

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

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

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)

Cites Work

• Open Shop Scheduling to Minimize Finish Time
• Short Shop Schedules
• When difference in machine loads leads to efficient scheduling in open shops
• Complexity results for flow-shop and open-shop scheduling problems with transportation delays
• 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
• Routing Two-Machine Flowshop Problems on Networks with Special Structure
• A Simple Heuristic for m-Machine Flow-Shop and its Applications in Routing-Scheduling Problems
• The museum visitor routing problem
• Transporting jobs through a two‐machine open shop
• A heuristic for the two-machine open-shop scheduling problem with transportation times
• Title not available (Why is that?)
• Completing partial schedules for open shop with unit processing times and routing
• Two-machine shop scheduling problems with batch processing
• Routing open shop with two nodes, unit processing times and equal number of jobs and machines
• On the routing open shop problem with two machines on a two-vertex network
• 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
• \(O(\log m)\)-approximation for the routing open shop problem
• The 2-Machine Routing Open Shop on a Triangular Transportation Network

Cited In (5)

• Two-machine routing open shop: How long is the optimal makespan?
• On the routing open shop problem with two machines on a two-vertex network
• Irreducible bin packing and normality in routing open shop
• 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

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)