Автор(ы): Лазарев А. А. (ИПУ РАН, Лаборатория 68)Кварацхелия А. Г. (ИПУ РАН, Лаборатория 68) НЕАКТУАЛЬНАЯ ЗАПИСЬГафаров Е. Р. (ИПУ РАН, Лаборатория 68)Автор(ов): 3 Параметры публикацииТип публикации: Статья в журнале/сборникеНазвание: Алгоритмы решения $NP$-трудной проблемы минимизации суммарного запаздывания для одного прибораНаименование источника: Доклады Академии наукОбозначение и номер тома: Т.412, №6Город: МоскваИздательство: НаукаГод издания: 2007Страницы: 739-742 АннотацияВ работе рассматривается классическая NP-трудная в обычном смысле проблема теории расписаний минимизации суммарного запаздывания для одного прибора $1\mid\,\mid\sum T_j$. Для NP-трудного случая задачи предложена процедура его разбиения на частные подслучаи,для которых приводятся полиномиальные и псевдополиномиальные алгоритмы решения, трудоемкости не превышающей $O(n^2\sum p_j)$. Библиографическая ссылка: Лазарев А.А., Кварацхелия А.Г., Гафаров Е.Р. Алгоритмы решения $NP$-трудной проблемы минимизации суммарного запаздывания для одного прибора // Доклады Академии наук. 2007. Т.412, №6. С. 739-742.