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