Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
On a Routing Open Shop Problem on Two Nodes with Unit Processing Times. / Golovachev, M. O.; Pyatkin, A. V.
в: Journal of Applied and Industrial Mathematics, Том 14, № 3, 01.08.2020, стр. 470-479.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - On a Routing Open Shop Problem on Two Nodes with Unit Processing Times
AU - Golovachev, M. O.
AU - Pyatkin, A. V.
N1 - Funding Information: The authors were supported by the Program of Basic Research of the Siberian Branch of the Russian Academy of Sciences (project no. 0314–2019–0014) and the Russian Foundation for Basic Research (project no. 20–01–00045). Publisher Copyright: © 2020, Pleiades Publishing, Ltd. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/8/1
Y1 - 2020/8/1
N2 - The Routing Open Shop Problem deals with n jobs located in the nodes of an edge-weightedgraph G=(V,E) and m machines that are initially in a special node calleddepot. The machines must process all jobs in arbitraryorder so that each machine processes at most one job at any one time and each job is processed byat most one machine at any one time. The goal is to minimize the makespan; i.e., the time whenthe last machine returns to the depot. This problem is known to be NP-hard even for the twomachines and the graph containing only two nodes. In this article we consider the particular caseof the problem with a 2-node graph, unitprocessing time of each job, and unit travel time between every two nodes. The conjecture is madethat the problem is polynomially solvable in this case; i.e., the makespan depends only on thenumber 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 inthe case of m = n depending on the loads distribution.
AB - The Routing Open Shop Problem deals with n jobs located in the nodes of an edge-weightedgraph G=(V,E) and m machines that are initially in a special node calleddepot. The machines must process all jobs in arbitraryorder so that each machine processes at most one job at any one time and each job is processed byat most one machine at any one time. The goal is to minimize the makespan; i.e., the time whenthe last machine returns to the depot. This problem is known to be NP-hard even for the twomachines and the graph containing only two nodes. In this article we consider the particular caseof the problem with a 2-node graph, unitprocessing time of each job, and unit travel time between every two nodes. The conjecture is madethat the problem is polynomially solvable in this case; i.e., the makespan depends only on thenumber 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 inthe case of m = n depending on the loads distribution.
KW - complexity
KW - makespan bound
KW - polynomial time
KW - routing open shop problem
KW - scheduling
KW - unit processing time
UR - http://www.scopus.com/inward/record.url?scp=85094654990&partnerID=8YFLogxK
U2 - 10.1134/S1990478920030060
DO - 10.1134/S1990478920030060
M3 - Article
AN - SCOPUS:85094654990
VL - 14
SP - 470
EP - 479
JO - Journal of Applied and Industrial Mathematics
JF - Journal of Applied and Industrial Mathematics
SN - 1990-4789
IS - 3
ER -
ID: 25993516