Изменения
Нет описания правки
Рассмотрим задачу <tex>1 \mid prec \mid f_{max}</tex>.
{{Задача
|definition = <wikitex>Дано $n$ работ, которые надо выполнить на одной машине, причем $i$-ая работа выполняется $p_i$ времени. Для каждой работы задана монотонно неубывающая функция $f_i$. Также между работами заданы отношения в виде ориентированного графа без циклов: если существует ребро $a \to b$, то работа $a$ должна завершиться до начала выполнения работы $b$. Необходимо построить такое расписание, чтобы величина $f_{max} = \max^{n}_\limits_{j=1}^{n}{f_j(C_j)}$, где $C_j$ {{---}} время окончания выполнения $j$-ой работы, была минимальна.</wikitex>
}}
<wikitex>Задача $1 \mid \mid f_{max}$ является частным случаем вышеописанной задачи. Здесь нет зависимостей между работами, то есть граф состоит из $n$ вершин и не содержит ребер. Очевидно, решив задачу в общем виде, мы также решим и эту.</wikitex>
<wikitex>Существует простой жадный алгоритм решения этой задачи, открытый Лаулером. Он заключается в том, чтобы строить расписание с конца.
Пусть $N = \{1, \dots, n\}$ {{---}} множество работ, и $S \subseteq N$ {{---}} множество работ, которых ещё нет в расписании. Пусть также $p(S) = \sum_sum\limits_{j \in S}{p_j}$. Тогда правило Лаулера можно сформулировать следующим образом: взять работу $j \in S$, у которой нет детей в графе зависимостей и имеющую минимальное значение $f_j(p(S))$, и сделать ее последней среди работ из $S$.
</wikitex>
===Реализация===
*<wikitextex>Пусть граф задан матрицей смежности $A = (a_{ij})$</tex> {{---}} матрица смежности графа, где $<tex>a_{ij} = 1$ </tex> тогда, и только тогда, когда существует ребро $<tex>i \to j$</tex>. За $*<tex>N(i)$ обозначим </tex> {{---}} число детей вершины $<tex>i$, а $</tex>.*<tex>\mathtt{schedule$ }</tex> {{---}} расписание.
'''for''' i = 1 '''to''' n
'''for''' j = 1 '''to''' n
P = sum(p[i])
'''for''' k = n '''downto''' 1
find job j in S with N[j] == 0 and minimal f[j](P)-value;
S = S \ {j}
N[i] = <tex>\infty</tex>
N[i]--
Сложность этого алгоритма $<tex>O(n^2)$.</wikitextex>.
===Доказательство===
