Том 14, серия 1, номер 2, 2007 г., Стр. 25-46

УДК 519.8
С. В. Севастьянов
Улучшенная аппроксимационная схема для задачи Джонсона с параллельными машинами

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

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

Статья поступила 27 июля 2006 г.
Исправленный вариант — 15 ноября 2006 г.