• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Алгоритмы решения NP-трудной проблемы минимизации суммарного запаздывания для одного прибора

Доклады Академии наук. 2007. Т. 412. № 6. С. 739-742.
Лазарев А. А., Кварацхелия А. Г., Гафаров Е. Р.

В работе рассматривается классическая NP-трудная в обычном смысле проблема теории расписаний минимизации суммарного запаздывания для одного прибора $1\mid\,\mid\sum T_j$. Для NP-трудного случая задачи предложена процедура его разбиения на частные подслучаи, для которых приводятся полиномиальные и псевдополиномиальные алгоритмы решения, трудоемкости не превышающей $O(n^2\sum p_j)$.