Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
On the two-machine routing open shop on a tree with preemption allowed. / Agzyamova, P. M.; Chernykh, I. D.
в: Siberian Electronic Mathematical Reports, Том 19, № 2, 2022, стр. 548-561.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - On the two-machine routing open shop on a tree with preemption allowed
AU - Agzyamova, P. M.
AU - Chernykh, I. D.
N1 - Funding Information: Agzyamova, P.M., Chernykh, I.D., On the two-machine routing open shop on a tree with preemption allowed. © 2022 Agzyamova P.M., Chernykh I.D. This research was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project FWNF-2022-0019), and supported by the Russian Foundation for Basic Research, projects 20-01-00045 and 20-07-00458. Received April, 21, 2022, published August, 26, 2022. Publisher Copyright: © 2022 Agzyamova P.M., Chernykh I.D.
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
KW - Asymmetric transportation network
KW - Individual travel times
KW - Polynomially solvable cases
KW - Restricted preemption
KW - Routing open shop
KW - Shop scheduling
KW - Standard lower bound
UR - http://www.scopus.com/inward/record.url?scp=85137639850&partnerID=8YFLogxK
UR - https://www.mendeley.com/catalogue/ea5ccfa0-1b0f-338e-80a2-3ffe6f599e39/
U2 - 10.33048/semi.2022.19.046
DO - 10.33048/semi.2022.19.046
M3 - Article
AN - SCOPUS:85137639850
VL - 19
SP - 548
EP - 561
JO - Сибирские электронные математические известия
JF - Сибирские электронные математические известия
SN - 1813-3304
IS - 2
ER -
ID: 37515234