Персональные инструменты
 

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

Материал из CustisWiki

Версия от 03:45, 24 августа 2005; BenderBot (обсуждение | вклад) (реплицировано из внутренней CustisWiki)

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

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

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

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

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

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


Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».

Репликация: База Знаний «Заказных Информ Систем» → «Составление расписаний»