A 6/5-approximation algorithm for the two-machine routing open-shop problem on a two-node network

In the routing open-shop problem, jobs are located at nodes of a transportation network, and the machines travel on the network to execute jobs. For the makespan-minimizing two-machine routing open-shop problem on a two-node network (which is NP-hard) we prove that the optimum objective value of any instance lies within the interval [&Ctilde;, 6/5&Ctilde;] and this interval is tight. &Ctilde; is a trivial lower bound on the optimum objective value. Based on this result, we obtain a linear time approximation algorithm for this problem with approximation ratio not greater than 6/5. From the tightness of the interval above it follows that this algorithm gives the best possible approximation in terms of &Ctilde;. The problem is equivalent to a variant of the two-machine open-shop problem with batch setup times with two batches.