Изменения

==Постановка задачи==Рассмотрим задачу <wikitextex>Рассмотрим задачу $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\limits_{j \in S}{p_j}$. Тогда правило Лаулера можно сформулировать следующим образом: взять работу $j \in S$, у которой нет детей в графе зависимостей и имеющую минимальное значение $f_j(p(S))$, и сделать ее последней среди работ из $S$.

==Правило Лаулера=Реализация===*<tex>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 N[i] += A[i][j] S = {1,...,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[j] = <tex>\infty</tex> schedule[k] = j P -= p[j] '''for''' i = 1 '''to''' n '''if''' A[i][j] == 1 N[i]-- Сложность этого алгоритма <tex>O(n^2)</tex>. ===Доказательство==={{Утверждение|statement=Вышеописанный алгоритм строит оптимальное расписание для задачи <tex>1 \mid prec \mid f_{max} </tex>.|proof=[[Файл:1.jpg]] <wikitex>Существует простой Пусть алгоритм решения этой задачипостроил расписание, в котором работы идут в порядке $1,2,\dots, открытый Лаулеромn$. Он заключается в томТакже пусть $\sigma : \sigma(1), \dots, чтобы строить \sigma(n)$ {{---}} оптимальное расписание с конца. Предположим, что $\sigma(i) = i$ для $i = n, n-1, \dots, r$ и $\sigma(r - 1) \ne r-1$, причем $r$ максимальное. Тогда имеем ситуацию, изображенную на рисунке выше.

Пусть Мы можем поставить работу $r - 1$ сразу перед $r$ по построению. Поэтому $r - 1$ и $j$ не имеют наследников в множестве $N = \{1, \dots, n\r-1}$ . Пусть $p_{{--r-1}} множество работ, $ и $S \subseteq Np_j$ есть времена, в которые выполняются работы $ {{r---}} множество незашедуленных работ. Пусть также 1$ и $p(S) = \sum_{j \in S}{p_j}$. Тогда правило Лаулера можно сформулировать следующим образом: взять работу Теперь, если мы поменяем работы $r-1$ и $j \in S$местами, то ответ не ухудшится. Действительно, у которой нет детей в графе зависимостей и имеющую минимальное значение $f_j(pp_{r-1}) \leqslant f_j(p_j)$ и $f_{r-1}(Sp_j)\leqslant f_j(p_j)$, а значения соответствующих функций для работ между $r-1$ и поставить ее на последнее место среди работы из $Sj$не изменятся, поэтому после перестановки ответ не ухудшится.