|
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.
Received April 21, 2022, published August 25, 2022
Citation:
A. V. Pyatkin, I. D. Chernykh, “On complexity of two-machine routing propotionate open shop”, Sib. Èlektron. Mat. Izv., 19:2 (2022), 528–539
Linking options:
https://www.mathnet.ru/eng/semr1519 https://www.mathnet.ru/eng/semr/v19/i2/p528
|
Statistics & downloads: |
Abstract page: | 92 | Full-text PDF : | 25 | References: | 19 |
|