Правило Лаулера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
==Постановка задачи==
 
==Постановка задачи==
<wikitex>Рассмотрим задачу $1 \mid prec \mid f_{max}$. Дано $n$ работ, которые надо выполнить на одной машине, причем $i$-ая работа выполняется $p_i$ времени. Для каждой работы задана монотонно неубывающая функция $f_i$. Также между работами заданы отношения в виде ориентированного графа без циклов: если существует ребро $a -> b$, то работа $a$ должна завершиться раньше работы $b$. Необходимо построить такое расписание, чтобы величина $f_{max} = max^{n}_{j=1}{f_j(C_j)}$, где $C_j$ {{---}} время окончания выполнения $j$-ой работы, была минимальна.
+
<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>
  
Строка 7: Строка 7:
  
 
Пусть $N = \{1, \dots, n\}$ {{---}} множество работ, и $S \subseteq N$ {{---}} множество незашедуленных работ. Пусть также $p(S) = \sum_{j \in S}{p_j}$. Тогда правило Лаулера можно сформулировать следующим образом: взять работу $j \in S$, у которой нет детей в графе зависимостей и имеющую минимальное значение $f_j(p(S))$, и поставить ее на последнее место среди работы из $S$.
 
Пусть $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>

Версия 02:21, 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>