|
Дискретная математика и математическая кибернетика
On the two-machine routing open shop on a tree with preemption allowed
P. M. Agzyamovaa, I. D. Chernykhb a Novosibirsk State University, 1, Pirogova str., Novosibirsk, 630090, Russia
b Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia
Аннотация:
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. To that end, we introduce a new problem setting with restricted preemption.
Ключевые слова:
shop scheduling, routing open shop, restricted preemption, individual travel times, asymmetric transportation network, polynomially solvable cases, standard lower bound.
Поступила 21 апреля 2022 г., опубликована 26 августа 2022 г.
Образец цитирования:
P. M. Agzyamova, I. D. Chernykh, “On the two-machine routing open shop on a tree with preemption allowed”, Сиб. электрон. матем. изв., 19:2 (2022), 548–561
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr1520 https://www.mathnet.ru/rus/semr/v19/i2/p548
|
Статистика просмотров: |
Страница аннотации: | 83 | PDF полного текста: | 21 | Список литературы: | 20 |
|