Аннотация:
In the routing open shop problem a fleet of mobile machines has to traverse the given transportation network, to process immovable jobs located at its nodes and to return back to the initial location in the shortest time possible. The problem is known to be NP-hard even for the simplest case with two machines and two nodes. We consider a special proportionate case of this problem, in which processing time for any job does not depend on a machine. We prove that the problem in this simplified setting is still NP-hard for the same simplest case. To that end, we introduce the new problem we call $2$-$\mathrm{Summing}$ and reduce it to the problem under consideration. We also suggest a $\frac76$-approximation algorithm for the two-machine proportionate problem with at most three nodes.
Ключевые слова:routing open shop, proportionate open shop, complexity, approximation algorithm, standard lower bound, optima localization.