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

Доклады Академии наук. 2010. Т. 432. № 6. С. 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$.

Ключевые слова: оптимизация, optimization, модели, models, scheduling theory, approximate algorithms, теория расписаний, приближенные алгоритмы, approximation algorithms, топология многообразий, исследование операций, аналитическая теория чисел