RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2022 Volume 19, Issue 2, Pages 528–539 (Mi semr1519)

Discrete mathematics and mathematical cybernetics

On complexity of two-machine routing propotionate open shop

A. V. Pyatkin, I. D. Chernykh

Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia

Abstract: 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.

Keywords: routing open shop, proportionate open shop, complexity, approximation algorithm, standard lower bound, optima localization.

UDC: 519.854.2

MSC: 90B35

Received April 21, 2022, published August 25, 2022

Language: English

DOI: 10.33048/semi.2022.19.044



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025