A 65-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 [C∼,65C∼] and this interval is tight. C∼ 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 65. From the tightness of the interval above it follows that this algorithm gives the best possible approximation in terms of C∼. The problem is equivalent to a variant of the two-machine open-shop problem with batch setup times with two batches.