TY - GEN

T1 - Two-Machine Routing Open Shop: How Long Is the Optimal Makespan?

AU - Chernykh, Ilya

N1 - Funding Information: This research was supported by the program of fundamental scientific researches of the SB RAS No I.5.1., project No 0314-2019-0014, and by the Russian Foundation for Basic Research, projects 20-01-00045 and 20-07-00458. Publisher Copyright: © 2021, Springer Nature Switzerland AG.

PY - 2021

Y1 - 2021

N2 - We consider a routing open shop problem being a natural generalization of the metric TSP and the classic open shop scheduling problem. The maximal possible ratio of the optimal makespan and the standard lower bound for the routing open shop has already been investigated in the last few years. The two-machine case is mostly covered. It is constructively proven in 2013 that the ratio mentioned above cannot be greater than 4/3, however, we do not know of any problem instance with the value of that ratio greater than 6/5. The latter ratio is achievable for a simplest case with two nodes. On the other hand, it is known that optimal makespan is at most 6/5 of the standard lower bound for at least a few special cases of the transportation network: one is with at most three nodes, and another is a tree. In this paper, we introduce an ultimate instance reduction technique, which allows reducing the general problem into a case with at most four nodes and at most six jobs. As a by-product, we propose a new polynomially solvable case of the two-machine routing open shop problem.

AB - We consider a routing open shop problem being a natural generalization of the metric TSP and the classic open shop scheduling problem. The maximal possible ratio of the optimal makespan and the standard lower bound for the routing open shop has already been investigated in the last few years. The two-machine case is mostly covered. It is constructively proven in 2013 that the ratio mentioned above cannot be greater than 4/3, however, we do not know of any problem instance with the value of that ratio greater than 6/5. The latter ratio is achievable for a simplest case with two nodes. On the other hand, it is known that optimal makespan is at most 6/5 of the standard lower bound for at least a few special cases of the transportation network: one is with at most three nodes, and another is a tree. In this paper, we introduce an ultimate instance reduction technique, which allows reducing the general problem into a case with at most four nodes and at most six jobs. As a by-product, we propose a new polynomially solvable case of the two-machine routing open shop problem.

KW - Efficient algorithm

KW - Instance reduction

KW - Optima localization

KW - Routing open shop

KW - Standard lower bound

UR - http://www.scopus.com/inward/record.url?scp=85111407457&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-77876-7_17

DO - 10.1007/978-3-030-77876-7_17

M3 - Conference contribution

AN - SCOPUS:85111407457

SN - 9783030778750

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

SP - 253

EP - 266

BT - Mathematical Optimization Theory and Operations Research - 20th International Conference, MOTOR 2021, Proceedings

A2 - Pardalos, Panos

A2 - Khachay, Michael

A2 - Kazakov, Alexander

PB - Springer Science and Business Media Deutschland GmbH

T2 - 20th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2021

Y2 - 5 July 2021 through 10 July 2021

ER -