Парето-оптимальное множество $NP$-трудной задачи минимизации максимального временного смещения

Известия РАН. Теория и системы управления. 2006. № 6. С. 103–110.

Лазарев А. А.

Рассматривается классическая NP-трудная в сильном смысле задача теории расписаний $1\mid r_j\mid L_{\max}$. Найдены новые свойства оптимальных расписаний. Выделен полиномиально-разрешимый случай задачи, когда моменты поступлений ($r_j$), продолжительности обслуживания ($p_j$) и директивные сроки завершения обслуживания($d_j$) требований удовлетворяют ограничениям: $d_1\le\dots\led_n\quad d_1-r_1-p_1\geq\dots\geq d_n-r_n-p_n$. Алгоритм трудоемкости $O(n^3\log n)$ находит Парето-оптимальное множество расписаний по критериям $L_{\max}$ и $C_{\max}$, содержащее не более $n$ вариантов.

Ключевые слова: оптимизация, optimization, оптимальные системы, теория графов, minimizing maximum time offset, scheduling theory, approximate algorithms, pareto-optimal set, $NP$, теория расписаний, приближенные алгоритмы, парето-оптимальное множество, $NP$, минимизация максимального временного смещения, approximation algorithms, методы исследования операций, исследование операций, нелинейные детерминированные системы