Составление расписаний

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

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

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

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

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

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