УПРАВЛЕНИЕ БОЛЬШИМИ СИСТЕМАМИ
на главную написать письмо карта сайта

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


Название статьи:  Метрика для задачи минимизации суммарного запаздывания
Выпуск: 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
Обсудить статью в Интернет-конференции по проблемам управления

Просмотров: 3235; загрузок: 1091, за месяц: 24.

Назад

ИПУ РАН © 2007. Все права защищены