Составление расписаний — различия между версиями

Текущая версия на 09:55, 4 августа 2008

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

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

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

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

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