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