EN|RU

Том 19, номер 3, 2012 г., Стр. 65-78

УДК 519.8
Пяткин А. В., Черных И. Д. 
Задача open shop с маршрутизацией на двухвершинной сети и разрешением прерываний

Аннотация:
Задача open shop с разрешением прерываний и маршрутизацией является обобщением двух классических задач дискретной оптимизации: NP-трудной метрической задачи коммивояжера и полиномиально разрешимой задачи теории расписаний open shop с разрешением прерываний. В статье рассматривается частный случай этой задачи, в котором транспортная сеть состоит из двух вершин. Показано, что задача с двумя машинами полиномиально разрешима, а для случая нефиксированного числа машин задача NP-трудна в сильномсмысле.
Ил. 6, библиогр. 6.

Ключевые слова: задача open shop с маршрутизацией, прерывание операций, NP-полнота.

Пяткин Артём Валерьевич 1
Черных Илья Дмитриевич 1,2

1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: artem@math.nsc.ru, idchern@math.nsc.ru

Статья поступила 8 августа 2011 г.
Исправленный вариант — 22 ноября 2011 г.

 © Институт математики им. С. Л. Соболева, 2015