Geodesic
On a routing Open Shop Problem on two nodes with unit processing times
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 3, pp. 53-70

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

The routing Open Shop Problem deals with $n$ jobs located in the nodes of an edge-weighted graph $G=(V,E)$ and $m$ machines that are initially in a special node called depot. The machines must process all jobs in arbitrary order so that each machine processes at most one job at any one time and each job is processed by at most one machine at any one time. The goal is to minimize the makespan; i. e., the time when the last machine returns to the depot. This problem is known to be NP-hard even for the two machines and the graph containing only two nodes. In this article we consider the particular case of the problem with a $2$-node graph, unit processing time of each job, and unit travel time between every two nodes. The conjecture is made that the problem is polynomially solvable in this case; i. e., the makespan depends only on the number of machines and the loads of the nodes and can be calculated in time $O(\log mn)$. We provide some new bounds on the makespan in the case of $m = n$ depending on the loads distribution. Tab. 2, bibliogr. 15.
Keywords: routing Open Shop Problem, unit processing time, complexity, scheduling, makespan bound.
Mots-clés : polynomial time 
@article{DA_2020_27_3_a2,
     author = {M. O. Golovachev and A. V. Pyatkin},
     title = {On a routing {Open} {Shop} {Problem} on two nodes with unit processing times},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {53--70},
     publisher = {mathdoc},
     volume = {27},
     number = {3},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_3_a2/}
}
TY  - JOUR
AU  - M. O. Golovachev
AU  - A. V. Pyatkin
TI  - On a routing Open Shop Problem on two nodes with unit processing times
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 53
EP  - 70
VL  - 27
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_3_a2/
LA  - ru
ID  - DA_2020_27_3_a2
ER  - 
%0 Journal Article
%A M. O. Golovachev
%A A. V. Pyatkin
%T On a routing Open Shop Problem on two nodes with unit processing times
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 53-70
%V 27
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2020_27_3_a2/
%G ru
%F DA_2020_27_3_a2
M. O. Golovachev; A. V. Pyatkin. On a routing Open Shop Problem on two nodes with unit processing times. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 3, pp. 53-70. http://geodesic.mathdoc.fr/item/DA_2020_27_3_a2/