6756

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Метрики в задачах теории расписаний

Наименование источника: 

  • Доклады Академии наук

Обозначение и номер тома: 

Т.432, №6

Город: 

  • Москва

Издательство: 

  • Наука

Год издания: 

2010

Страницы: 

746-749
Аннотация
Одним из актуальных вопросов разработки математической теориирасписаний является построение метрик, которые можно использоватьпри разработке точных и приближенных алгоритмов решения задач.Введение метрических пространств для $NP$-трудных задач теориирасписаний позволяет применять общие математические подходы кнахождению приближенного решения с гарантированной абсолютнойпогрешностью.Ранее для $NP$-трудных задач с критерием минимизации максимальноговременн\'ого смещения $\{P,R,Q\}|prec,r_j|\{L_{\max},C_{\max}\}$была получена метрика в пространстве примеров (исходных параметровзадачи), на основе которой была разработана общая схема нахожденияприближенных решений. В настоящей работепредложен поход к нахождению метрик в пространстве примеров длязадач с суммарными критериями: $\sum T_j$, $\sum w_jT_j$, $\sumw_jC_j$, $\sum w_j U_j$.

Библиографическая ссылка: 

Лазарев А.А., Кварацхелия А.Г. Метрики в задачах теории расписаний // Доклады Академии наук. 2010. Т.432, №6. С. 746-749.