Правило Лаулера

Постановка задачи

<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>

Доказательство

Утверждение:

Вышеописанный алгоритм строит оптимальное расписание для задачи [math]1 \mid prec \mid f_{max} [/math].

[math]\triangleright[/math]

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

[math]\triangleleft[/math]