Правило Лаулера — различия между версиями
Smolcoder (обсуждение | вклад) |
Smolcoder (обсуждение | вклад) (→Правило Лаулера) |
||
| Строка 10: | Строка 10: | ||
===Реализация=== | ===Реализация=== | ||
| − | <wikitex>Пусть граф задан матрицей смежности $A = (a_{ij})$, где $a_{ij} = 1$ тогда, и только тогда, когда существует ребро $i \to j$. За $ | + | <wikitex>Пусть граф задан матрицей смежности $A = (a_{ij})$, где $a_{ij} = 1$ тогда, и только тогда, когда существует ребро $i \to j$. За $N(i)$ обозначим число детей вершины $i$, а $schedule$ - расписание. |
for i = 1 to n do | for i = 1 to n do | ||
for j = 1 to n do | for j = 1 to n do | ||
| Строка 27: | Строка 27: | ||
Сложность этого алгоритма $O(n^2)$. | Сложность этого алгоритма $O(n^2)$. | ||
| + | </wikitex> | ||
| + | |||
| + | ===Доказательство=== | ||
| + | <wikitex>{{Утверждение | ||
| + | |statement= | ||
| + | Вышеописанный алгоритм строит оптимальное расписание. | ||
| + | |proof= | ||
| + | Пусть алгоритм построил расписание, в котором работы идут в порядке $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$ минимальное. | ||
| + | }} | ||
</wikitex> | </wikitex> | ||
Версия 02:34, 9 мая 2012
Постановка задачи
<wikitex>Рассмотрим задачу $1 \mid prec \mid f_{max}$. Дано $n$ работ, которые надо выполнить на одной машине, причем $i$-ая работа выполняется $p_i$ времени. Для каждой работы задана монотонно неубывающая функция $f_i$. Также между работами заданы отношения в виде ориентированного графа без циклов: если существует ребро $a \to b$, то работа $a$ должна завершиться раньше работы $b$. Необходимо построить такое расписание, чтобы величина $f_{max} = max^{n}_{j=1}{f_j(C_j)}$, где $C_j$ — время окончания выполнения $j$-ой работы, была минимальна. </wikitex>
Правило Лаулера
<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>
Реализация
<wikitex>Пусть граф задан матрицей смежности $A = (a_{ij})$, где $a_{ij} = 1$ тогда, и только тогда, когда существует ребро $i \to j$. За $N(i)$ обозначим число детей вершины $i$, а $schedule$ - расписание.
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[i] = inf;
schedule[k] = j;
P -= p[j];
for i = 1 to n do
if A[i][j] = 1 then
n[i]--;
Сложность этого алгоритма $O(n^2)$. </wikitex>
Доказательство
<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$ минимальное. |
</wikitex>
