Просмотр исходного текста страницы Составление расписаний

Задача «Составление расписаний» заключается в следующем:

Имеется ''m'' одинаковых машин и ''n'' независимых работ с заданными
длительностями исполнения ''t<sub>1</sub>,…,t<sub>n</sub>''. Требуется распределить
эти работы по машинам так, чтобы минимизировать максимальную
загрузку (загрузка машины равна сумме длительностей работ,
приписанных данной машине).

Несмотря на простоту постановки эта задача трудна с вычислительной
точки зрения (NP-полна). Традиционный подход к таким задачам состоит в
использовании простых эвристик.

Например:
«Берется произвольная работа и помещается на машину,
имеющую наименьшую загрузку».

При этом, можно доказать следующее утвержение: «Построенное расписание отличается от оптимального (по критерию минимизации максимальной загрузки) не более, чем в два раза».


[[Category:Алгоритмы]]
{{replicate-from-custiswiki-to-lib}}