  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.
