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

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

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

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

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

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

---

Внимание! Данная статья выбрана для репликации во внешнюю базу знаний компании. Пожалуйста, не допускайте в этой статье публикацию конфиденциальной информации, ведения обсуждений в теле статьи, и более ответственно относитесь к качеству самой статьи — проверяйте орфографию, пишите по-русски, избегайте непроверенной вами информации.