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/

[1] I. Averbakh, O. Berman, I. Chernykh, “A 6/5-approximation algorithm for the two-machine routing open-shop problem on a two-node network”, Eur. J. Oper. Res., 166:1 (2005), 3–24 | DOI | MR | Zbl

[2] I. Averbakh, O. Berman, I. Chernykh, “The routing open-shop problem on a network: complexity and approximation”, Eur. J. Oper. Res., 173:2 (2006), 531–539 | DOI | MR | Zbl

[3] I. Chernykh, Two-machine routing open shop: How long is the optimal makespan?, Mathematical optimization theory and operations research, 20th international conference, MOTOR 2021, Proceedings, Springer Lect. Notes Comput. Sci., 12755, eds. Pardalos Panos (ed.) et al., Springer, Cham, 2021, 253–266 | DOI | MR | Zbl

[4] I. Chernykh, A. Kononov, S. Sevastyanov, “Efficient approximation algorithms for the routing open shop problem”, Comput. Oper. Res., 40:3 (2013), 841–847 | DOI | MR | Zbl

[5] I. Chernykh, E. Lgotina, “The 2-machine routing open shop on a triangular transportation network”, Discrete optimization and operations research, 9th international conference, DOOR 2016, Proceedings (Vladivostok, Russia, September 19-23, 2016), Lecture Notes in Computer Science, 9869, eds. Kochetov Yury (ed.) et al., 2016, 284–297 | DOI | MR | Zbl

[6] I. Chernykh, A. Pyatkin, “Irreducible bin packing and normality in routing open shop”, Ann. Math. Artif. Intell., 89:8-9 (2021), 899–918 | DOI | MR | Zbl

[7] M. Garey, D. Johnson, Computers and intractability: A guide to the theory of NP-completeness, W.H. Freeman Co., San Francisco, 1979 | MR | Zbl

[8] T. Gonzalez, S. Sahni, “Open shop scheduling to minimize finish time”, J. Assoc. Comput. Mach., 23 (1976), 665–679 | DOI | MR | Zbl

[9] A. Khramova, I. Chernykh, “A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing”, J. Sched., 24:4 (2021), 405–412 | DOI | MR | Zbl

[10] A. Kononov, “On the routing open shop problem with two machines on a two-vertex network”, J. Appl. Ind. Math., 6:3 (2012), 318–331 | DOI | MR | Zbl

[11] A Kononov, S. Sevastianov, I. Tchernykh, “When difference in machine loads leads to efficient scheduling in open shops”, Ann. Oper. Res., 92 (1999), 211–239 | DOI | MR | Zbl

[12] C. Koulamas, G. Kyparisis, “The three-machine proportionate open shop and mixed shop minimum makespan problems”, Eur. J. Oper. Res., 243:1 (2015), 70–74 | DOI | MR | Zbl

[13] E. Lawler, J. Lenstra, A. Rinnooy Kan, D. Shmoys, “Sequencing and scheduling: Algorithms and complexity”, Logistics Of Production And Inventory, Handbooks in Operations Research and Management Science, 4, Elsevier, 1993, 445–522 | DOI | MR

[14] C. Liu, R. Bulfin, “Scheduling ordered open shops”, Comput. Oper. Res., 14 (1987), 257–264 | DOI | MR | Zbl

[15] M. Matta, S. Elmaghraby, “Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop”, Eur. J. Oper. Res., 201:3 (2010), 720–728 | DOI | MR | Zbl

[16] B. Naderi, M. Zandieh, M. Yazdani, “Polynomial time approximation algorithms for proportionate open-shop scheduling”, Int. Trans. Oper. Res., 21:6 (2014), 1031–1044 | DOI | MR | Zbl

[17] S. Sevastyanov, “Some positive news on the proportionate open shop problem”, Sib. Èlektron. Mat. Izv., 16 (2019), 406–426 | DOI | MR | Zbl

[18] S. Sevastyanov, I. Tchernykh, “Computer-aided way to prove theorems in scheduling”, Algorithms - ESA'98Algorithms – ESA '98, 6th annual European symposium, Proceedings (Venice, Italy, August 24-26, 1998), Lect. Notes Comput. Sci., 1461, eds. Bilardi Gianfranco (ed.) et al., Springer, Berlin, 1998, 502–513 | DOI | MR | Zbl

[19] D. Williamson, L. Hall, J. Hoogeveen, C. Hurkens, J. Lenstra, S. Sevast'janov, D. Shmoys, “Short shop schedules”, Oper. Res., 45:2 (1997), 288–294 | DOI | MR | Zbl