Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
On the Optima Localization for the Three-Machine Routing Open Shop. / Chernykh, Ilya; Krivonogova, Olga.
Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings. ed. / Alexander Kononov; Michael Khachay; Valery A. Kalyagin; Panos Pardalos. Springer Gabler, 2020. p. 274-288 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12095 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - On the Optima Localization for the Three-Machine Routing Open Shop
AU - Chernykh, Ilya
AU - Krivonogova, Olga
PY - 2020/1/1
Y1 - 2020/1/1
N2 - A tight optima localization interval for the classical open shop scheduling problem with three machines was established by S. Sevastyanov and I. Chernykh in 1998. It was proved that for any problem instance its optimal makespan does not exceed$$\frac{4}{3}$$ times the standard lower bound. The process of proof involved massive computer-aided enumeration of the subsets of instances of the problem considered and took about 200 h of the running time to complete. This makes it seemingly impossible to use the same approach for more complicated problems, i.e. the four machine open shop for which the optima localization interval is still unknown. In this paper we apply that computer-aided approach to the three-machine routing open shop problem on a two-node transportation network. For this generalization of the plain open shop problem we derive some extreme instance properties and prove that the optimal makespan does not exceed$$\frac{4}{3}$$ times the standard lower bound, thus generalizing the result previously known for the three-machine open shop.
AB - A tight optima localization interval for the classical open shop scheduling problem with three machines was established by S. Sevastyanov and I. Chernykh in 1998. It was proved that for any problem instance its optimal makespan does not exceed$$\frac{4}{3}$$ times the standard lower bound. The process of proof involved massive computer-aided enumeration of the subsets of instances of the problem considered and took about 200 h of the running time to complete. This makes it seemingly impossible to use the same approach for more complicated problems, i.e. the four machine open shop for which the optima localization interval is still unknown. In this paper we apply that computer-aided approach to the three-machine routing open shop problem on a two-node transportation network. For this generalization of the plain open shop problem we derive some extreme instance properties and prove that the optimal makespan does not exceed$$\frac{4}{3}$$ times the standard lower bound, thus generalizing the result previously known for the three-machine open shop.
KW - Approximation algorithm
KW - Computer-aided proof
KW - Open shop
KW - Optima localization
KW - Routing open shop
UR - http://www.scopus.com/inward/record.url?scp=85087790898&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-49988-4_19
DO - 10.1007/978-3-030-49988-4_19
M3 - Conference contribution
AN - SCOPUS:85087790898
SN - 9783030499877
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 274
EP - 288
BT - Mathematical Optimization Theory and Operations Research - 19th International Conference, MOTOR 2020, Proceedings
A2 - Kononov, Alexander
A2 - Khachay, Michael
A2 - Kalyagin, Valery A.
A2 - Pardalos, Panos
PB - Springer Gabler
T2 - 19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020
Y2 - 6 July 2020 through 10 July 2020
ER -
ID: 24737005