Advertisement
Published in:
2020 | OriginalPaper | Chapter
On the Optima Localization for the Three-Machine Routing Open Shop
Authors : Ilya Chernykh, Olga Krivonogova
Published in: Mathematical Optimization Theory and Operations Research
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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.