|
Дискретный анализ и исследование операций, 2012, том 19, выпуск 3, страницы 65–78
(Mi da691)
|
|
|
|
Эта публикация цитируется в 7 научных статьях (всего в 7 статьях)
Задача open shop с маршрутизацией на двухвершинной сети и разрешением прерываний
А. В. Пяткинa, И. Д. Черныхab a Институт математики им. С. Л. Соболева СО РАН, Новосибирск, Россия
b Новосибирский гос. дарственный университет, Новосибирск, Россия
Аннотация:
Задача open shop с разрешением прерываний и маршрутизацией является обобщением двух классических задач дискретной оптимизации: NP-трудной метрической задачи коммивояжёра и полиномиально разрешимой задачи теории расписаний open shop с разрешением прерываний. В статье рассматривается частный случай этой задачи, в котором транспортная сеть состоит из двух вершин. Показано, что задача с двумя машинами полиномиально разрешима, а для случая нефиксированного числа машин задача NP-трудна в сильном смысле. Ил. 6, библиогр. 6.
Ключевые слова:
задача open shop с маршрутизацией, прерывание операций, NP-полнота.
Статья поступила: 08.08.2011 Переработанный вариант: 22.11.2011
Образец цитирования:
А. В. Пяткин, И. Д. Черных, “Задача open shop с маршрутизацией на двухвершинной сети и разрешением прерываний”, Дискретн. анализ и исслед. опер., 19:3 (2012), 65–78; J. Appl. Industr. Math., 6:3 (2012), 346–354
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da691 https://www.mathnet.ru/rus/da/v19/i3/p65
|
Статистика просмотров: |
Страница аннотации: | 493 | PDF полного текста: | 125 | Список литературы: | 47 | Первая страница: | 7 |
|