355
правок
Изменения
Нет описания правки
==Правило Лаулера==
===Формулировка===
<wikitex>Существует простой жадный алгоритм решения этой задачи, открытый Лаулером. Он заключается в том, чтобы строить расписание с конца.
Пусть $N = \{1, \dots, n\}$ {{---}} множество работ, и $S \subseteq N$ {{---}} множество незашедуленных работ. Пусть также $p(S) = \sum_{j \in S}{p_j}$. Тогда правило Лаулера можно сформулировать следующим образом: взять работу $j \in S$, у которой нет детей в графе зависимостей и имеющую минимальное значение $f_j(p(S))$, и поставить ее на последнее место среди работы из $S$.
</wikitex>
}}
[[Категория: Теория расписаний]]
[[Категория: Жадные алгоритмы]]
