А. В. Кононов, “О цеховой задаче открытого типа на двух машинах с маршрутизацией в двухвершинной сети”, Дискретн. анализ и исслед. опер., 2012, том 19, выпуск 2,страницы 54

Эта публикация цитируется в 15 статьях

О цеховой задаче открытого типа на двух машинах с маршрутизацией в двухвершинной сети

А. В. Кононов^ab

^a Институт математики им. С. Л. Соболева СО РАН, Новосибирск, Россия
^b Новосибирский гос. университет, Новосибирск, Россия

Аннотация: Рассматривается цеховая задача открытого типа для двух машин с маршрутизацией в двухвершинной сети. Задача является NP-трудной. Для её решения предлагаются точный псевдополиномиальный алгоритм и вполне полиномиальная приближённая схема и выделяются полиномиально разрешимые случаи. Ил. 6, табл. 1, библиогр. 8.

Ключевые слова: цеховая задача открытого типа, маршрутизация, вполне полиномиальная приближённая схема.

УДК: 519.2+621.391

Статья поступила: 09.06.2011
Переработанный вариант: 24.11.2011