|
Дискретная математика и математическая кибернетика
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
Аннотация:
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.
Поступила 21 апреля 2022 г., опубликована 25 августа 2022 г.
Образец цитирования:
A. V. Pyatkin, I. D. Chernykh, “On complexity of two-machine routing propotionate open shop”, Сиб. электрон. матем. изв., 19:2 (2022), 528–539
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr1519 https://www.mathnet.ru/rus/semr/v19/i2/p528
|
Статистика просмотров: |
Страница аннотации: | 94 | PDF полного текста: | 25 | Список литературы: | 20 |
|