TY - JOUR

T1 - Two-machine routing open shop on a tree

T2 - instance reduction and efficiently solvable subclass

AU - Chernykh, I. D.

AU - Lgotina, E. V.

N1 - Publisher Copyright: © 2020 Informa UK Limited, trading as Taylor & Francis Group.

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

KW - instance reduction

KW - open shop with delays

KW - overloaded edge

KW - overloaded node

KW - polynomially solvable subclass

KW - routing open shop

KW - Scheduling

KW - standard lower bound

KW - ALGORITHM

KW - SCHEDULING PROBLEMS

KW - FLOWSHOP

KW - JOBS

KW - COMPLEXITY

UR - http://www.scopus.com/inward/record.url?scp=85081352932&partnerID=8YFLogxK

U2 - 10.1080/10556788.2020.1734802

DO - 10.1080/10556788.2020.1734802

M3 - Article

AN - SCOPUS:85081352932

VL - 36

SP - 821

EP - 841

JO - Optimization Methods and Software

JF - Optimization Methods and Software

SN - 1055-6788

IS - 4

ER -