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

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.

Keywords:

• Scheduling
• open shop with delays
• routing open shop
• standard lower bound
• instance reduction
• polynomially solvable subclass
• overloaded node
• overloaded edge

2010 Mathematics Subject Classification:

• 90B35

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research was supported by the program of fundamental scientific researches of the SB RAS No I.5.1., project No 0314-2019-0014, and by the Russian Foundation for Basic Research, projects 20-01-00045, 20-07-00458 and 18-01-00747.

Notes on contributors

I. D. Chernykh

I. D. Chernykh is a senior researcher from Sobolev Institute of Mathematics, Novosibirsk, Russia. He received his M.S. in Novosibirsk State University in 1996 and Russian analogue of a Ph.D. degree (candidate of sciences) in 2001. His main area of research interest lies within machine scheduling, including but no limited to the design of efficient approximation algorithms and computer-aided proofs.

E. V. Lgotina

E. V. Lgotina is a second year master student at Novosibirsk State University, Faculty of Mechanics and Mathematics, studying for Master's degree in Mechanics and Mathematical Modelling. Along with her studies, she carries out scientific research in two different scientific areas. For the last five years, she has been investigating optima localization problems for various routing open shop models. She also has research experience in hydraulic fracturing, in particular, she works on interpretation of the minifrac.