Geodesic
On complexity of two-machine routing propotionate open shop
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 528-539

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{SEMR_2022_19_2_a27,
     author = {A. V. Pyatkin and I. D. Chernykh},
     title = {On complexity of two-machine routing propotionate open shop},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {528--539},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a27/}
}
TY  - JOUR
AU  - A. V. Pyatkin
AU  - I. D. Chernykh
TI  - On complexity of two-machine routing propotionate open shop
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2022
SP  - 528
EP  - 539
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a27/
LA  - en
ID  - SEMR_2022_19_2_a27
ER  - 
%0 Journal Article
%A A. V. Pyatkin
%A I. D. Chernykh
%T On complexity of two-machine routing propotionate open shop
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2022
%P 528-539
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a27/
%G en
%F SEMR_2022_19_2_a27
A. V. Pyatkin; I. D. Chernykh. On complexity of two-machine routing propotionate open shop. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 528-539. http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a27/