https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%A1%D0%BE%D1%81%D1%82%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D0%B8%D1%81%D0%B0%D0%BD%D0%B8%D0%B9 2026-05-02T10:37:36Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=%D0%A1%D0%BE%D1%81%D1%82%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D0%B8%D1%81%D0%B0%D0%BD%D0%B8%D0%B9&diff=1291&oldid=prev 2008-08-04T09:55:53Z

<p>1 версия</p> <p><b>Новая страница</b></p><div>Задача «Составление расписаний» заключается в следующем:<br /> <br /> Имеется ''m'' одинаковых машин и ''n'' независимых работ с заданными<br /> длительностями исполнения ''t&lt;sub&gt;1&lt;/sub&gt;,…,t&lt;sub&gt;n&lt;/sub&gt;''. Требуется распределить<br /> эти работы по машинам так, чтобы минимизировать максимальную<br /> загрузку (загрузка машины равна сумме длительностей работ,<br /> приписанных данной машине).<br /> <br /> Несмотря на простоту постановки эта задача трудна с вычислительной<br /> точки зрения (NP-полна). Традиционный подход к таким задачам состоит в<br /> использовании простых эвристик.<br /> <br /> Например:<br /> «Берется произвольная работа и помещается на машину,<br /> имеющую наименьшую загрузку».<br /> <br /> При этом, можно доказать следующее утвержение: «Построенное расписание отличается от оптимального (по критерию минимизации максимальной загрузки) не более, чем в два раза».<br /> <br /> <br /> [[Category:Алгоритмы]]<br /> {{replicate-from-custiswiki-to-lib}}</div>

WikiSysop