TY - GEN

T1 - Approximation Algorithms for Two-Machine Proportionate Routing Open Shop on a Tree

AU - Chernykh, Ilya

AU - Krivonogova, Olga

AU - Shmyrina, Anna

N1 - The research was supported by Russian Science Foundation grant N 22-71-10015, https://rscf.ru/en/project/22-71-10015/.

PY - 2023

Y1 - 2023

N2 - The routing open shop problem is a natural generalization of the open shop problem and the metric traveler salesman problem. Jobs are located at the nodes of a transportation network, which has to be traversed by mobile machines in order to process the operations of the jobs, similar to the classic open shop environment. We consider the proportionate special case of this problem, in which for each job processing times of its operations are equal. This problem is known to be NP-hard even for the simplest case with two machines and two nodes. We present the tight optima localization interval for the two-machine problem with asymmetric transportation network being arbitrary tree, yielding a 76 -approximation algorithm for this problem. Surprisingly, the same result holds for a more general problem where travel times are machine-dependent under the special condition, when one machine is “not faster” than the other. This stands in contrast to the general routing open shop (without the proportionate condition), for which optima localization intervals are different for identical travel times and uniform travel times cases.

AB - The routing open shop problem is a natural generalization of the open shop problem and the metric traveler salesman problem. Jobs are located at the nodes of a transportation network, which has to be traversed by mobile machines in order to process the operations of the jobs, similar to the classic open shop environment. We consider the proportionate special case of this problem, in which for each job processing times of its operations are equal. This problem is known to be NP-hard even for the simplest case with two machines and two nodes. We present the tight optima localization interval for the two-machine problem with asymmetric transportation network being arbitrary tree, yielding a 76 -approximation algorithm for this problem. Surprisingly, the same result holds for a more general problem where travel times are machine-dependent under the special condition, when one machine is “not faster” than the other. This stands in contrast to the general routing open shop (without the proportionate condition), for which optima localization intervals are different for identical travel times and uniform travel times cases.

KW - Approximation algorithms

KW - Optima localization

KW - Proportionate open shop

KW - Routing open shop

KW - Unrelated travel times

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85164912947&origin=inward&txGid=9a9282dedaed5bf4c7afe611cf81be8d

UR - https://www.mendeley.com/catalogue/074ff3aa-21a0-3862-ac22-fe7661453adf/

U2 - 10.1007/978-3-031-35305-5_13

DO - 10.1007/978-3-031-35305-5_13

M3 - Conference contribution

SN - 9783031353048

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 197

EP - 211

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

PB - Springer Science and Business Media Deutschland GmbH

ER -