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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
м (Доказательство)
(не показано 13 промежуточных версий 2 участников)
Строка 1: Строка 1:
==Постановка задачи==
+
Рассмотрим задачу <tex>1 \mid prec \mid f_{max}</tex>.
<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$-ой работы, была минимальна.
+
{{Задача
 
+
|definition = <wikitex>Дано $n$ работ, которые надо выполнить на одной машине, причем $i$-ая работа выполняется $p_i$ времени. Для каждой работы задана монотонно неубывающая функция $f_i$. Также между работами заданы отношения в виде ориентированного графа без циклов: если существует ребро $a \to b$, то работа $a$ должна завершиться до начала выполнения работы $b$. Необходимо построить такое расписание, чтобы величина $f_{max} = \max\limits_{j=1..n}{f_j(C_j)}$, где $C_j$ {{---}} время окончания выполнения $j$-ой работы, была минимальна.</wikitex>
Задача $1 \mid \mid f_{max}$ является частным случаем вышеописанной задачи. Здесь нет зависимостей между работами, то есть граф состоит из $n$ вершин и не содержит ребер. Очевидно, решив задачу в общем виде, мы также решим и эту.
+
}}
</wikitex>
+
<wikitex>Задача $1 \mid \mid f_{max}$ является частным случаем вышеописанной задачи. Здесь нет зависимостей между работами, то есть граф состоит из $n$ вершин и не содержит ребер. Очевидно, решив задачу в общем виде, мы также решим и эту.</wikitex>
  
 
==Правило Лаулера==
 
==Правило Лаулера==
 
===Формулировка===
 
===Формулировка===
<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$.
+
Пусть $N = \{1, \dots, n\}$ {{---}} множество работ, и $S \subseteq N$ {{---}} множество работ, которых ещё нет в расписании. Пусть также $p(S) = \sum\limits_{j \in S}{p_j}$. Тогда правило Лаулера можно сформулировать следующим образом: взять работу $j \in S$, у которой нет детей в графе зависимостей и имеющую минимальное значение $f_j(p(S))$, и сделать ее последней среди работ из $S$.
 
</wikitex>
 
</wikitex>
  
 
===Реализация===
 
===Реализация===
<wikitex>Пусть граф задан матрицей смежности $A = (a_{ij})$, где $a_{ij} = 1$ тогда, и только тогда, когда существует ребро $i \to j$. За $N(i)$ обозначим число детей вершины $i$, а $schedule$ - расписание.
+
*<tex>A = (a_{ij})</tex> {{---}} матрица смежности графа, где <tex>a_{ij} = 1</tex> тогда, и только тогда, когда существует ребро <tex>i \to j</tex>.
  for i = 1 to n do
+
*<tex>N(i)</tex> {{---}} число детей вершины <tex>i</tex>.
   for j = 1 to n do
+
*<tex>\mathtt{schedule}</tex> {{---}} расписание.
       N[i] += A[i][j];
+
  '''for''' i = 1 '''to''' n
  S = {1,...,n};
+
   '''for''' j = 1 '''to''' n
  P = sum(p[i]);
+
       N[i] += A[i][j]
  for k = n downto 1 do
+
  S = {1,...,n}
   find job j in S with N[j] = 0 and minimal f[j](P)-value;
+
  P = sum(p[i])
   S = S \ {j};
+
  '''for''' k = n '''downto''' 1
   N[i] = inf;
+
   find job j in S with N[j] == 0 and minimal f[j](P)-value
   schedule[k] = j;
+
   S = S \ {j}
   P -= p[j];
+
   N[j] = <tex>\infty</tex>
   for i = 1 to n do
+
   schedule[k] = j
     if A[i][j] = 1 then
+
   P -= p[j]
       N[i]--;
+
   '''for''' i = 1 '''to''' n
 +
     '''if''' A[i][j] == 1
 +
       N[i]--
  
Сложность этого алгоритма $O(n^2)$.
+
Сложность этого алгоритма <tex>O(n^2)</tex>.
</wikitex>
 
  
 
===Доказательство===
 
===Доказательство===
Строка 37: Строка 38:
 
Вышеописанный алгоритм строит оптимальное расписание для задачи <tex>1 \mid prec \mid f_{max} </tex>.
 
Вышеописанный алгоритм строит оптимальное расписание для задачи <tex>1 \mid prec \mid f_{max} </tex>.
 
|proof=
 
|proof=
<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]]
[[Файл:1.jpg|right]]
+
 
Мы можем поставить работу $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>Пусть алгоритм построил расписание, в котором работы идут в порядке $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}$. Пусть $p_{r-1}$ и $p_j$ есть времена, в которые выполняются работы $r-1$ и $j$. Теперь, если мы поменяем работы $r-1$ и $j$ местами, то ответ не ухудшится. Действительно, $f_j(p_{r-1}) \leqslant f_j(p_j)$ и $f_{r-1}(p_j) \leqslant f_j(p_j)$, а значения соответствующих функций для работ между $r-1$ и $j$ не изменятся, поэтому после перестановки ответ не ухудшится.
 
</wikitex>
 
</wikitex>
 
}}
 
}}
  
==Источники==
+
==См. также==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8
+
*[[Flow shop]]
 +
*[[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
 +
 
 +
==Источники информации==
 +
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 62-63 стр. {{---}} ISBN 978-3-540-69515-8
  
 +
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Версия 23:02, 8 июня 2015

Рассмотрим задачу [math]1 \mid prec \mid f_{max}[/math].

Задача:
<wikitex>Дано $n$ работ, которые надо выполнить на одной машине, причем $i$-ая работа выполняется $p_i$ времени. Для каждой работы задана монотонно неубывающая функция $f_i$. Также между работами заданы отношения в виде ориентированного графа без циклов: если существует ребро $a \to b$, то работа $a$ должна завершиться до начала выполнения работы $b$. Необходимо построить такое расписание, чтобы величина $f_{max} = \max\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$. </wikitex>

Реализация

  • [math]A = (a_{ij})[/math] — матрица смежности графа, где [math]a_{ij} = 1[/math] тогда, и только тогда, когда существует ребро [math]i \to j[/math].
  • [math]N(i)[/math] — число детей вершины [math]i[/math].
  • [math]\mathtt{schedule}[/math] — расписание.
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] = [math]\infty[/math]
  schedule[k] = j
  P -= p[j]
  for i = 1 to n
    if A[i][j] == 1
      N[i]--

Сложность этого алгоритма [math]O(n^2)[/math].

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

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

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$ не имеют наследников в множестве ${1,\dots,r-1}$. Пусть $p_{r-1}$ и $p_j$ есть времена, в которые выполняются работы $r-1$ и $j$. Теперь, если мы поменяем работы $r-1$ и $j$ местами, то ответ не ухудшится. Действительно, $f_j(p_{r-1}) \leqslant f_j(p_j)$ и $f_{r-1}(p_j) \leqslant f_j(p_j)$, а значения соответствующих функций для работ между $r-1$ и $j$ не изменятся, поэтому после перестановки ответ не ухудшится.

</wikitex>
[math]\triangleleft[/math]

См. также

Источники информации

  • Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 62-63 стр. — ISBN 978-3-540-69515-8