Sufficient conditions of polynomial solvability of the two-machine preemptive routing open shop on a tree

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

The routing open shop problem with preemption allowed is a natural combination of the metric TSP problem and the classical preemptive open shop scheduling problem. While metric TSP is strongly NP-hard, the preemptive open shop is polynomially solvable for any (even unbounded) number of machines. The previous research on the preemptive routing open shop is mostly focused on the case with just two nodes of the transportation network (problem on a link). It is known to be strongly NP-hard in the case of an unbounded number of machines and polynomially solvable for the two-machine case. The algorithmic complexity of both two-machine problem on a triangular network and a three-machine problem with two nodes are still unknown. The problem with a general transportation network is a generalization of the metric TSP and therefore is strongly NP-hard. We describe a wide polynomially solvable subclass of the preemptive routing open shop on a tree. This class allows building an optimal schedule with at most one preemption in linear time. For any instance from that class optimal makespan coincides with the standard lower bound. Therefore, the result, previously known for the problem on a link, is generalized on a special case on an arbitrary tree. The algorithmic complexity of the general case of the two-machine problem on a tree remains unknown.

Язык оригиналаанглийский
Название основной публикацииOptimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers
РедакторыYury Kochetov, Michael Khachay, Yury Evtushenko, Vlasta Malkova, Mikhail Posypkin, Milojica Jacimovic
ИздательSpringer-Verlag GmbH and Co. KG
Страницы97-110
Число страниц14
ISBN (печатное издание)9783030109332
DOI
СостояниеОпубликовано - 1 янв 2019
Событие9th International Conference on Optimization and Applications, OPTIMA 2018 - Petrovac, Черногория
Продолжительность: 1 окт 20185 окт 2018

Серия публикаций

НазваниеCommunications in Computer and Information Science
Том974
ISSN (печатное издание)1865-0929

Конференция

Конференция9th International Conference on Optimization and Applications, OPTIMA 2018
СтранаЧерногория
ГородPetrovac
Период01.10.201805.10.2018

Fingerprint Подробные сведения о темах исследования «Sufficient conditions of polynomial solvability of the two-machine preemptive routing open shop on a tree». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Chernykh, I. (2019). Sufficient conditions of polynomial solvability of the two-machine preemptive routing open shop on a tree. В Y. Kochetov, M. Khachay, Y. Evtushenko, V. Malkova, M. Posypkin, & M. Jacimovic (Ред.), Optimization and Applications - 9th International Conference, OPTIMA 2018, Revised Selected Papers (стр. 97-110). (Communications in Computer and Information Science; Том 974). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-10934-9_7