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

Автор(ы): Лазарев А. А., Коренев П. С., Сологуб А. А.

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

Выпуск: 57

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

Год: 2015

Библиография: Лазарев А. А., Коренев П. С., Сологуб А. А. Метрика для задачи минимизации суммарного запаздывания / Управление большими системами. Выпуск 57. М.: ИПУ РАН, 2015. С.123-137.

Дата опубликования: 30.09.2015

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

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

Author(s): Lazarev A., Korenev P., Sologub A.

Article title: Metric for minimum total delay problem

Issue: 57

Year: 2015

Keywords: scheduling theory, approximation algorithms, NPhardness, metrics

Abstract: We consider the NP-hard 1|rj|PTj scheduling problem and suggest the polynomial time algorithm to find its approximate solution with the guaranteed absolute error. The algorithm employs the metric introduced in the parameter space. We also consider possible application of such an approach to the other scheduling problems.

в формате PDF
Обсудить статью в Интернет-конференции по проблемам управления

Просмотров: 34; загрузок: 1134, за месяц: 16.

Назад