Geodesic
On the two-machine routing open shop on a tree with preemption allowed
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 548-561.

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

The routing open shop problem is a natural generalization of the metric TSP and a classical open shop scheduling problem. Jobs are located at the nodes of a given transportation network, and mobile machines have to perform operations on those jobs while traveling over the edges. Machines are obligated to return to the initial location after completing all operations. The goal is to minimize the makespan. We consider the two-machine routing open shop on a tree with preemption in a general setting, where travel times are machine- and direction-dependent. For this problem we describe a wide polynomially solvable special case, for which the optimal makespan is guaranteed to coincide with the standard lower bound. To that end, we introduce a new problem setting with restricted preemption.
Keywords: shop scheduling, routing open shop, restricted preemption, individual travel times, asymmetric transportation network, polynomially solvable cases, standard lower bound. 
@article{SEMR_2022_19_2_a28,
     author = {P. M. Agzyamova and I. D. Chernykh},
     title = {On the two-machine routing open shop on a tree with preemption allowed},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {548--561},
     publisher = {mathdoc},
     volume = {19},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a28/}
}
TY  - JOUR
AU  - P. M. Agzyamova
AU  - I. D. Chernykh
TI  - On the two-machine routing open shop on a tree with preemption allowed
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2022
SP  - 548
EP  - 561
VL  - 19
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a28/
LA  - en
ID  - SEMR_2022_19_2_a28
ER  - 
%0 Journal Article
%A P. M. Agzyamova
%A I. D. Chernykh
%T On the two-machine routing open shop on a tree with preemption allowed
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2022
%P 548-561
%V 19
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a28/
%G en
%F SEMR_2022_19_2_a28
P. M. Agzyamova; I. D. Chernykh. On the two-machine routing open shop on a tree with preemption allowed. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 19 (2022) no. 2, pp. 548-561. http://geodesic.mathdoc.fr/item/SEMR_2022_19_2_a28/

[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] O. Braun, G. Schmidt, “Parallel processor scheduling with limited number of preemptions”, SIAM J. Comput., 32:3 (2003), 671–680 | DOI | MR | Zbl

[4] I. Chernykh, “Routing open shop with unrelated travel times”, 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, 272–283 | DOI | MR | Zbl

[5] I. Chernykh, “Sufficient conditions of polynomial solvability of the two-machine preemptive routing open shop on a tree”, Optimization and applications, 9th international conference, OPTIMA 2018, Revised selected papers (Petrovac, Montenegro, October 1-5, 2018), Comput. Inf. Sci., 974, eds. Evtushenko Yury (ed.) et al., 2019, 97–110 | MR | Zbl

[6] 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

[7] I. Chernykh, O. Krivonogova, “Efficient algorithms for the routing open shop with unrelated travel times on cacti”, Optimization and applications, 10th international conference, OPTIMA 2019, Revised selected papers (Petrovac, Montenegro, September 30 – October 4, 2019), Commun. Comput. Inf. Sci., 1145, eds. Jaćimović Milojica (ed.) et al., Springer, Cham, 2020, 1–15 | MR | Zbl

[8] I. Chernykh, M. Kuzevanov, “Sufficient condition of polynomial solvability of two-machine routing open shop with preemption allowed”, Intellektual'nye Sistemy, 17 (2013), 552–556 | MR

[9] I. Chernykh, E. Lgotina, “How the difference in travel times affects the optima localization for the routing open shop”, Mathematical optimization theory and operations research, 18th international conference, MOTOR 2019 (Ekaterinburg, Russia, July 8-12, 2019), Lect. Notes Comput. Sci., 11548, eds. Khachay Michael (ed.) et al., Springer, Cham, 2019, 187–201 | DOI | MR | Zbl

[10] I. Chernykh, E. Lgotina, “Two-machine routing open shop on a tree: instance reduction and efficiently solvable subclass”, Optimization Methods And Software, 2020 | DOI | MR

[11] N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Technical Report No 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburg, PA, 1976 | MR

[12] A. Dugarzhapov, A. Kononov, “A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job”, J. Sched., 19:1 (2016), 61–72 | DOI | MR | Zbl

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

[14] 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

[15] 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

[16] A. Kononov, “$O(\log m)$-approximation for the routing open shop problem”, RAIRO, Oper. Res., 49:2 (2015), 383–391 | DOI | MR | Zbl

[17] A. Kononov, S. Sevastyanov, M. Sviridenko, “A Complete 4-parametric complexity classification of short shop scheduling problems”, J. Sched., 15:4 (2012), 427–446 | DOI | MR | Zbl

[18] 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

[19] 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

[20] M. Pinedo, L. Schrage, “Stochastic shop scheduling: A survey, Deterministic and stochastic scheduling” (Durham/Engl., 1981), Proc. NATO Adv. Study Res. Inst., 1982, 181–196 | MR | Zbl

[21] A. Pyatkin, I. Chernykh, “The open shop problem with routing at a two-node network and allowed preemption”, J. Appl. Ind. Math., 6:3 (2012), 346–354 | DOI | MR | Zbl

[22] S. Sevastyanov, I. Tchernykh, “Computer-aided way to prove theorems in scheduling”, Algorithms - 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

[23] S. Sevastianov, G. Woeginger, “Makespan minimization in open shops: A polynomial time approximation scheme”, Math. Program., 82:1-2 (1998), 191–198 | DOI | MR | Zbl

[24] A. Soper, “A cyclical search for the two machine flow shop and open shop to minimise finishing time”, J. Sched., 18:3 (2015), 311–314 | DOI | MR | Zbl

[25] D. de Werra, “Graph-theoretical models for preemptive scheduling”, Advances In Project Scheduling, 1989, 171–185 | DOI | MR

[26] 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