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