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

Материал из DISCOPAL
Версия от 09:55, 4 августа 2008; WikiSysop (обсуждение) (1 версия)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

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

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

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

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.