Минимизация максимального временно́го смещения для одного прибора

Рассматривается классическая $NP$-трудная задача теории расписаний $1|r_j|L_\mathrm{max}$. Представлен алгоритм нахождения оптимального расписания обслуживания $n$ требований (работ), когда параметры требований удовлетворяют системе линейных ограничений. Расширена полиномиально разрешимая область задачи $1|r_j|L_\mathrm{max}$. Представлен алгоритм построения Парето-оптимального множества расписаний по критериям $L_\mathrm{max}$ и $C_\mathrm{max}$ трудоемкости $O(n^3 \log n)$ операций.

Статья представлена к публикации членом редколлегии: Ф. Т. Алескеров