• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

Лазарев А. А., Архипов Д. И.

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