EN|RU

Том 19, номер 2, 2012 г., Стр. 55-75

УДК 519.95
Кононов А. В. 
О цеховой задаче открытого типа на двух машинах с маршрутизацией в двухвершинной сети

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

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

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

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

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