Изменения

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

*<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 do '''for ''' j = 1 '''to ''' n do N[i] += A[i][j]; S = {1,...,n}; P = sum(p[i]); '''for ''' k = n '''downto ''' 1 do find job j in S with N[j] == 0 and minimal f[j](P)-value; S = S \ {j}; N[ij] = inf;<tex>\infty</tex> schedule[k] = j; P -= p[j]; '''for ''' i = 1 '''to ''' n do '''if ''' A[i][j] == 1 then N[i]--;

Сложность этого алгоритма $<tex>O(n^2)$.</wikitextex>.

[[Файл: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$ минимальноемаксимальное. Тогда имеем ситуацию, изображенную на рисунке:выше. [[Файл:1.jpg|right]]Мы можем поставить работу $r - 1$ сразу перед $r$ по построению. Поэтому $r - 1$ и $j$ не имеют наследников в множестве ${1,\dots,r-1}$. Теперь если мы сместим блок работ между Пусть $p_{r-1}$ и $p_j$ есть времена, в которые выполняются работы $r-1$ влевои $j$. Теперь, поставив если мы поменяем работы $r-1$ перед и $rj$местами, то время окончания каждой работы из этого блока только уменьшится, и значения соответствующих функций ответ не увеличатся по монотонностиухудшится. АДействительно, так как $f_j(p_{r-1}) \leqslant f_j(p_j)$ и $f_{r-1}(pp_j) \le leqslant f_j(pp_j)$, где а значения соответствующих функций для работ между $p = \sum^{r-1}_{i=1}{p_i}$, то и $f_{max}j$ не увеличится. Проделывая описанное далееизменятся, мы придем к тому расписанию, который строит наш алгоритм, без ухудшения ответапоэтому после перестановки ответ не ухудшится.

==См. также==*[[Flow shop]]*[[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]] ==Источникиинформации==* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 62-63 стр. {{---}} ISBN 978-3-540-69515-8