А. А. Лазарев, П. С. Коренев, А. А. Сологуб, “Метрика для задачи минимизации суммарного запаздывания”, УБС, 2015, выпуск 57,страницы 123

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

Управление в социально-экономических системах

Метрика для задачи минимизации суммарного запаздывания

А. А. Лазарев, П. С. Коренев, А. А. Сологуб

ФГБУН Институт проблем управления им. В.А. Трапезникова РАН

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

Ключевые слова: теория расписаний, приближенные алгоритмы, NP-трудность, метрики.

УДК: 519.854.2
ББК: 22.1

Поступила в редакцию: 23 июня 2015 г.
Опубликована: 30 сентября 2015 г.