RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирские электронные математические известия // Архив

Сиб. электрон. матем. изв., 2022, том 19, выпуск 2, страницы 528–539 (Mi semr1519)

Дискретная математика и математическая кибернетика

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.

УДК: 519.854.2

MSC: 90B35

Поступила 21 апреля 2022 г., опубликована 25 августа 2022 г.

Язык публикации: английский

DOI: 10.33048/semi.2022.19.044



Реферативные базы данных:


© МИАН, 2024