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/