1outtreesumwc — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(добавлено доказательство оптимальности)
м (rollbackEdits.php mass rollback)
 
(не показано 20 промежуточных версий 5 участников)
Строка 1: Строка 1:
{{В разработке}}
 
 
 
<tex dpi = "200" >1 \mid outtree \mid \sum w_i C_i</tex>
 
<tex dpi = "200" >1 \mid outtree \mid \sum w_i C_i</tex>
  
== Постановка задачи ==
+
{{Задача
Мы должны составить расписание с произвольными временами обработки на одном станке. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы исходящим деревом {{---}} работа, которая соответствует корню, доступна в начале, все другие работы зависят от одной работы {{---}} отца в дереве. Тривиальным примером подобной задачи является демонтаж сложного механизма.
+
|definition=
 +
Необходимо составить расписание на одном станке работ с произвольными временами выполнения. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы исходящим [[Дерево, эквивалентные определения | деревом]] {{---}} работа, которая соответствует корню, доступна в начале, все другие работы зависят от одной работы {{---}} отца в дереве.  
 +
}}
 +
Тривиальным примером подобной задачи является демонтаж сложного механизма.
  
 
== Свойства оптимального расписания ==
 
== Свойства оптимального расписания ==
Строка 10: Строка 11:
 
Докажем некоторые свойства оптимального расписания, которые мы будем использовать в доказательстве корректности алгоритма.
 
Докажем некоторые свойства оптимального расписания, которые мы будем использовать в доказательстве корректности алгоритма.
  
Введем некоторые обозначения для удобства. За <tex> edges </tex> обозначим список всех ребёр дерева. Для всех работ <tex>i = 1, ..., n</tex> обозначим обозначим за <tex>S(i)</tex> всех потомков <tex>i</tex> в дереве зависимостей, включая саму работу <tex>i</tex>, введём новый парамерт работы <tex dpi = 150>q_i = \frac{w_i}{p_i}</tex>.  
+
Введем некоторые обозначения для удобства. За <tex>\mathrm{edges} </tex> обозначим список всех ребёр дерева. Для всех работ <tex>i = 1, \ldots, n</tex> обозначим за <tex>S(i)</tex> всех потомков <tex>i</tex> в дереве зависимостей, включая саму работу <tex>i</tex>, введём новый параметр работы <tex>q_i = \dfrac{w_i}{p_i}</tex>.  
  
Для подмножества работ <tex>I \subseteq \{1, ..., n\}</tex> определим:
+
Для подмножества работ <tex>I \subseteq \{1, \ldots, n\}</tex> определим:
  
<tex dpi = 150>w(I) = \sum\limits_{i \in I} w_i, p(I) = \sum\limits_{i \in I} p_i, q(I) = \frac{w(I)}{p(I)}</tex>
+
<tex>w(I) = \sum\limits_{i \in I} w_i, p(I) = \sum\limits_{i \in I} p_i, q(I) = \dfrac{w(I)}{p(I)}</tex>
  
Два непересекающихся множества работ <tex>I, J \subseteq \{1, ..., n\}</tex> будем называть ''параллельными'' <tex>(I \sim J)</tex>, если для всех <tex>i \in I, j \in J</tex> выполняется: <tex>i</tex> не является ни предком, ни потомком <tex>j</tex>. Если множества состоят из одной работы <tex>I = \{i\}, J = \{j\}</tex>, будем писать <tex>i \sim j</tex>. Каждое расписание представлено перестановкой <tex>\pi</tex>.
+
Два непересекающихся множества работ <tex>I, J \subseteq \{1, \ldots, n\}</tex> будем называть '''параллельными''' <tex>(I \sim J)</tex>, если для всех <tex>i \in I, j \in J</tex> выполняется: <tex>i</tex> не является ни предком, ни потомком <tex>j</tex>. Если множества состоят из одной работы <tex>I = \{i\},\ J = \{j\}</tex>, будем писать <tex>i \sim j</tex>. Каждое расписание представлено перестановкой <tex>\pi</tex>.
  
 
{{Лемма
 
{{Лемма
 
|id=lemma1
 
|id=lemma1
 
|statement= Пусть <tex>\pi</tex> {{---}} оптимальное расписание, <tex>I</tex> и <tex>J</tex> {{---}} два таких параллельных блока (множества работ, выполняемых последовательно) из <tex>\pi</tex>, что <tex>J</tex> выполняется сразу после <tex>I</tex>. Пусть <tex>\pi'</tex> {{---}} расписание, полученное из <tex>\pi</tex> перестановкой <tex>I</tex> и <tex>J</tex>. Тогда выполяются следующие пункты:
 
|statement= Пусть <tex>\pi</tex> {{---}} оптимальное расписание, <tex>I</tex> и <tex>J</tex> {{---}} два таких параллельных блока (множества работ, выполняемых последовательно) из <tex>\pi</tex>, что <tex>J</tex> выполняется сразу после <tex>I</tex>. Пусть <tex>\pi'</tex> {{---}} расписание, полученное из <tex>\pi</tex> перестановкой <tex>I</tex> и <tex>J</tex>. Тогда выполяются следующие пункты:
<tex>(a)~ I \sim J \Rightarrow q(I) \geqslant q(J)</tex>  
+
:<tex>(a)~ I \sim J \Rightarrow q(I) \geqslant q(J)</tex>  
<tex>(b)</tex> Если <tex>I \sim J</tex> и <tex>q(I) = q(J)</tex>, то <tex>\pi'</tex> {{---}} оптимальное расписание.
+
:<tex>(b)</tex> Если <tex>I \sim J</tex> и <tex>q(I) = q(J)</tex>, то <tex>\pi'</tex> {{---}} оптимальное расписание.
 
|proof=  
 
|proof=  
<tex>(a)</tex> Пусть <tex>f = \sum w_i C_i</tex>. Так как <tex>\pi</tex> {{---}} оптимальное расписание, то <tex>f(\pi) \leqslant f(\pi')</tex>. Таким образом:
+
<tex>(a)</tex>  
  
<tex>0 \leqslant f(\pi') - f(\pi) = w(I) p(J) - w(J) p(I)</tex>
+
:Пусть <tex>f = \sum w_i C_i</tex>. Так как <tex>\pi</tex> {{---}} оптимальное расписание, то <tex>f(\pi) \leqslant f(\pi')</tex>. Таким образом:
  
Поделим на <tex>p(I)p(J)</tex>:
+
:<tex>0 \leqslant f(\pi') - f(\pi) = w(I) p(J) - w(J) p(I)</tex>
  
<tex dpi = 150>q(I) = \frac{w(I)}{p(I)} \geqslant \frac{w(J)}{p(J)} = q(J) </tex>  
+
:Поделим на <tex>p(I)p(J)</tex>:
  
<tex>(b)</tex> Если <tex>q(I) = q(J) </tex>, то <tex>f(\pi) = f(\pi') </tex>, следовательно расписание <tex>\pi'</tex> оптимально.
+
:<tex>q(I) = \dfrac{w(I)}{p(I)} \geqslant \dfrac{w(J)}{p(J)} = q(J) </tex>
 +
 
 +
<tex>(b)</tex>  
 +
 
 +
:Если <tex>q(I) = q(J) </tex>, то <tex>f(\pi) = f(\pi') </tex>, следовательно расписание <tex>\pi'</tex> оптимально.
 
}}
 
}}
  
 
{{Теорема
 
{{Теорема
 
|id = theorem1
 
|id = theorem1
|statement = Пусть <tex>i, ~j</tex> работы такие, что <tex>i</tex> {{---}} потомок <tex>j</tex>, и <tex> q_j = \max \{q_k \mid ~ (i, k) \in edges \}</tex>. <br>
+
|statement = Пусть <tex>i, ~j</tex> работы такие, что <tex>i</tex> {{---}} предок <tex>j</tex>, и <tex> q_j = \max \{q_k \mid ~ (i, k) \in \mathrm{edges} \}</tex>. <br>
 
Тогда существует оптимальное расписание, в котором работа <tex>j</tex> идёт сразу после работы <tex>i</tex>
 
Тогда существует оптимальное расписание, в котором работа <tex>j</tex> идёт сразу после работы <tex>i</tex>
 
|proof =  
 
|proof =  
Каждое расписание может быть представлено последовательностью работ в порядке, в котором они выполняются. Пусть <tex> \pi </tex> будет оптимальной такой последовательностью со свойством, что количество работ между <tex> i </tex> и <tex> j </tex> равное <tex> l </tex> было бы минимальным. Можно считать, что <tex> l > 0 </tex>. Тогда расписание можно представить следующим образом:
+
Каждое расписание может быть представлено последовательностью работ в порядке, в котором они выполняются. Пусть <tex> \pi </tex> будет оптимальной такой последовательностью. Также предположим, что количество работ между <tex> i </tex> и <tex> j </tex> равное <tex> l </tex> было бы минимальным. Можно считать, что <tex> l > 0 </tex>. Тогда расписание можно представить следующим образом:
  
//TODO: картинка i ... k j
+
[[Файл:JobBlock.jpg]]
  
Рассмотрим 2 случая.
+
Рассмотрим <tex>2</tex> случая.
  
 
'''Случай 1''': <tex> k \in S(i) </tex>
 
'''Случай 1''': <tex> k \in S(i) </tex>
  
Работа <tex> j </tex> не является потомком работы <tex> k </tex> , иначе у неё было бы <tex>2</tex> предка. Следовательно, <tex> k \sim j </tex>. По [[#lemma1 | лемме]] <tex> q(k) \geqslant q(j) </tex>, а по условию выбора <tex> j </tex> имеем <tex> q(j) \geqslant q(k) </tex>, значит, <tex> q(j) = q(k) </tex>. Опять же из [[#lemma1 | леммы]] следует, что работы <tex> k </tex> и <tex> j </tex> можно поменять местами, не ухудшив расписание. Это противоречит тому, что мы выбрали минимальное <tex> l </tex>.
+
:Работа <tex> j </tex> не является потомком работы <tex> k </tex> , иначе у неё было бы <tex>2</tex> предка. Следовательно, <tex> k \sim j </tex>. По [[#lemma1 | лемме]] <tex> q(k) \geqslant q(j) </tex>, а по условию выбора <tex> j </tex> имеем <tex> q(j) \geqslant q(k) </tex>, значит, <tex> q(j) = q(k) </tex>. Опять же из [[#lemma1 | леммы]] следует, что работы <tex> k </tex> и <tex> j </tex> можно поменять местами, не ухудшив расписание. Это противоречит тому, что мы выбрали минимальное <tex> l </tex>.
  
 
'''Случай 2''': <tex> k \not\in S(i) </tex>
 
'''Случай 2''': <tex> k \not\in S(i) </tex>
Пусть <tex> h </tex> будет последней работой в расписании между <tex> i </tex> и <tex> j </tex> <tex> ( </tex> включая работу <tex> i) </tex>, которая принадлежит <tex> S(i) </tex>, то есть для всех работ <tex> r </tex> в множестве <tex> K </tex> назначенных между <tex> h </tex> и <tex> j </tex> имеем, что <tex> r \not\in S(i) </tex>. Так как наш граф зависимостей работ является исходящим деревом и  <tex>(i, j) \in edges </tex>, то любой предок работы <tex> j </tex> также является и предком работы <tex> i </tex>. Поэтому никакая работа из <tex> K </tex> не является предком <tex> j </tex> <tex>(</tex>иначе бы она не смогла стоять после <tex> i) </tex> или потомком, значит, <tex> K \sim j </tex>. Из этого следует, что <tex> q(K) \geqslant q(j) </tex>.
 
  
Работа <tex> h \in S(i) </tex> не является потомком какой-либо работы <tex> r \in K </tex>. В противном же случае получалось, что <tex> r \in S(i) </tex>, значит, <tex> h </tex> является не последней работой из <tex> S(i) </tex> между <tex> i </tex> и <tex> j </tex>. Поэтому <tex> h \sim K </tex>, откуда тут же следует, что <tex> q(h) \geqslant q(K) \geqslant q(j) </tex>. По определению <tex> j </tex> имеем, что <tex> q(j) \geqslant q(h) </tex>, следовательно <tex> q(j) = q(h) = q(K) </tex>. По [[#lemma1 | лемме]] мы можем поменять блоки <tex> K </tex> и <tex> j </tex> не нарушив оптимальности расписания.
+
:Пусть <tex> h </tex> будет последней работой в расписании между <tex> i </tex> и <tex> j\ ( </tex>включая работу <tex> i) </tex>, которая принадлежит <tex> S(i) </tex>, то есть для всех работ <tex> r </tex> в множестве <tex> K </tex>, назначенных между <tex> h </tex> и <tex> j </tex>, имеем, что <tex> r \not\in S(i) </tex>. Так как наш [[Основные определения теории графов | граф]] зависимостей работ является исходящим деревом и  <tex>(i, j) \in \mathrm{edges} </tex>, то любой предок работы <tex> j </tex> также является и предком работы <tex> i </tex>. Поэтому никакая работа из <tex> K </tex> не является предком <tex> j\ (</tex>иначе бы она не смогла стоять после <tex> i) </tex> или потомком, значит, <tex> K \sim j </tex>. Из этого следует, что <tex> q(K) \geqslant q(j) </tex>.
 +
 
 +
:Работа <tex> h \in S(i) </tex> не является потомком какой-либо работы <tex> r \in K </tex>. В противном же случае получалось, что <tex> r \in S(i) </tex>, значит, <tex> h </tex> является не последней работой из <tex> S(i) </tex> между <tex> i </tex> и <tex> j </tex>. Поэтому <tex> h \sim K </tex>, откуда тут же следует, что <tex> q(h) \geqslant q(K) \geqslant q(j) </tex>. По определению <tex> j </tex> имеем, что <tex> q(j) \geqslant q(h) </tex>, следовательно <tex> q(j) = q(h) = q(K) </tex>. По [[#lemma1 | лемме]] мы можем поменять блоки <tex> K </tex> и <tex> j </tex> не нарушив оптимальности расписания.
 +
 
 +
Таким образом мы можем менять соседние работы или блоки работ, пока <tex> j </tex> не окажется сразу за <tex> i </tex>.
 
}}
 
}}
  
Строка 64: Строка 72:
  
 
Детали описаны в алгоритме ниже, в котором
 
Детали описаны в алгоритме ниже, в котором
* <tex> E(i) </tex> обозначает последнюю работу в последовательности <tex> \pi_i </tex>
+
* <tex> E(i) </tex> обозначает последнюю работу в последовательности <tex> \pi_i </tex>,
 
* <tex> P(i) </tex> обозначает предка в графе зависимостей, а после слияния с какой-то вершиной <tex> j </tex> {{---}} предыдущую работу в последовательности <tex> \pi_j </tex>.
 
* <tex> P(i) </tex> обозначает предка в графе зависимостей, а после слияния с какой-то вершиной <tex> j </tex> {{---}} предыдущую работу в последовательности <tex> \pi_j </tex>.
  
 
   w[root] = <tex> - \infty </tex>
 
   w[root] = <tex> - \infty </tex>
   '''for''' i = 1..n:
+
   '''for''' i = 1..n
     E[i] = {i}, J[i] = {i}, q[i] = w[i] \ p[i]
+
     E[i] = {i}  
 +
    J[i] = {i}  
 +
    q[i] = w[i] \ p[i]
 
   L = {1, ... , n}
 
   L = {1, ... , n}
   '''while''' L <tex> \ne </tex> {root}: // пока в списке работ не останется только корень
+
   '''while''' L <tex> \ne </tex> {root} <font color=darkgreen>// пока в списке работ не останется только корень</font>
     Найти работу j <tex> \in </tex> L с маскимальным значением q[j]
+
     Найти работу j <tex> \in </tex> L с максимальным значением q[j]
 
     par = P[j]
 
     par = P[j]
 
     Найти i, что par <tex> \in </tex> J[i]
 
     Найти i, что par <tex> \in </tex> J[i]
 
     w[i] += w[j]
 
     w[i] += w[j]
 
     p[i] += p[j]
 
     p[i] += p[j]
     q[i] = w[i] / w[j]    // пересчитаем значения в вершине
+
     q[i] = w[i] / w[j]    <font color=darkgreen>// пересчитаем значения в вершине</font>
     P[j] = E[i]          // предком работы j теперь будет последняя работа в <tex> \pi_i </tex>
+
     P[j] = E[i]          <font color=darkgreen>// предком работы j теперь будет последняя работа в <tex> \pi_i </tex></font>
     E[i] = E[j]          // последней работой в <tex> \pi_i </tex> теперь будет последняя работа в <tex> \pi_j </tex>
+
     E[i] = E[j]          <font color=darkgreen>// последней работой в <tex> \pi_i </tex> теперь будет последняя работа в <tex> \pi_j </tex></font>
 
     J[i] = J[i] <tex> \cup </tex> J[j]
 
     J[i] = J[i] <tex> \cup </tex> J[j]
 
     L = L \ {j}
 
     L = L \ {j}
Строка 86: Строка 96:
 
После завершения этой процедуры оптимальное расписание можно восстановить с конца, зная <tex> E(root) </tex> и массив <tex> P </tex>.
 
После завершения этой процедуры оптимальное расписание можно восстановить с конца, зная <tex> E(root) </tex> и массив <tex> P </tex>.
  
Если для получения работы <tex> j </tex> с минимальным значением <tex> q(j) </tex> использовать очередь с приоритетами, а для поиска родителям вершины использовать систему непересекающихся множеств, то время работы алгоритма будет <tex> O(n\log{n}) </tex>.
+
Если для получения работы <tex> j </tex> с минимальным значением <tex> q(j) </tex> использовать очередь с приоритетами, а для поиска родителям вершины использовать систему непересекающихся множеств, то время работы алгоритма будет <tex> \mathcal{O}(n\log{n}) </tex>.
 +
 
 +
Проиллюстрируем работу алгоритма на следующем примере.
 +
 
 +
[[Файл:JobsOuttrees.jpg|650px]]
 +
 
 +
Первой выберется работа с номером <tex> 5 </tex>. Она объединится со своим родителем <tex> 2 </tex> и допишется в конец <tex> \pi_2 </tex>. Потом выберется работа <tex> 4 </tex>, потом <tex> \{2, 5\} </tex> и т. д. Процесс будет продолжаться, пока не останется одна вершина. Ответ {{---}} оптимальная последовательность работ {{---}} содержится в <tex> \pi_1 </tex>, который написан внутри последней вершины.
  
 
== Доказательство оптимальности алгоритма ==
 
== Доказательство оптимальности алгоритма ==
Строка 93: Строка 109:
 
|statement = Алгоритм <tex> 1 \mid outtree \mid \sum w_i C_i</tex> строит оптимальное расписание.
 
|statement = Алгоритм <tex> 1 \mid outtree \mid \sum w_i C_i</tex> строит оптимальное расписание.
 
|proof =  
 
|proof =  
Доказательство проведём по индукции. Очевидно, что для одной вершины алгоритм построит оптимальное расписание. Пусть теперь он может составить оптимальную последовательность назначенных работ числом меньше <tex> n </tex>. Пусть также работы <tex> i, j </tex> {{---}} работы, которые объединяться на первом шаге алгоритма. Тогда оптимальное расписание <tex> R </tex> можно представить следующим образом:
+
Доказательство проведём по индукции. Очевидно, что для одной вершины алгоритм построит оптимальное расписание. Пусть теперь он может составить оптимальную последовательность назначенных работ числом меньше <tex> n </tex>. Пусть также работы <tex> i, j </tex> {{---}} работы, которые объединятся на первом шаге алгоритма. Тогда оптимальное расписание <tex> R </tex> можно представить следующим образом:
  
<tex> \pi \colon \pi (1), ..., \pi (k), i, j, \pi (k + 3), ..., \pi (n) </tex>
+
<tex> \pi \colon \pi (1), \ldots, \pi (k), i, j, \pi (k + 3), \ldots, \pi (n) </tex>
  
 
После объединения работ <tex> i </tex> и <tex> j </tex> в одну расписание <tex> R' </tex> примет такой вид:
 
После объединения работ <tex> i </tex> и <tex> j </tex> в одну расписание <tex> R' </tex> примет такой вид:
  
<tex> \pi ' \colon \pi (1), ..., \pi (k), I, \pi (k + 3), ..., \pi (n) </tex>
+
<tex> \pi ' \colon \pi (1), \ldots, \pi (k), I, \pi (k + 3), \ldots, \pi (n) </tex>
  
где <tex> I = \{i, j\}, ~w(I) = w(i) + w(j), p(I) = p(i) + p(j)</tex>. Обозначим за <tex> f_n(\pi ), ~f_{n-1}(\pi ') </tex> целевые функции для последовательностей <tex> \pi </tex> и <tex> \pi ' </tex> соответственно. Тогда
+
где <tex> I = \{i, j\}, ~w(I) = w(i) + w(j), p(I) = p(i) + p(j)</tex>. Обозначим за <tex> f_n(\pi ), ~f_{n-1}(\pi ') </tex> целевые функции для последовательностей <tex> \pi </tex> и <tex> \pi ' </tex> соответственно. Тогда  
  
<tex>
+
<tex> f_n(\pi ) - f_{n-1}(\pi') = w(i)p(i) + w(j)(p(i) + p(j)) - (w(i) + w(j))(p(i) + p(j)) = -w(i) p(j)\ (*) </tex>
f_n(\pi ) - f_{n-1}(\pi ') \\ = w(i)p(i) + w(j)(p(i) + p(j)) - (w(i) + w(j))(p(i) + p(j)) = -w(i)p(j) ~(*)
 
</tex>
 
  
 
Следовательно, расписание <tex> R </tex> будет оптимальным тогда и только тогда, когда расписание <tex> R' </tex> будет оптимальным. А по предположению индукции наш алгоритм составит оптимальное расписание для последовательности <tex> \pi ' </tex>.
 
Следовательно, расписание <tex> R </tex> будет оптимальным тогда и только тогда, когда расписание <tex> R' </tex> будет оптимальным. А по предположению индукции наш алгоритм составит оптимальное расписание для последовательности <tex> \pi ' </tex>.
Строка 111: Строка 125:
 
Теперь разделим обе части равенства <tex> (*) </tex> на <tex> w(i)w(j) </tex>. Получим, что расстояние между целевыми функциями равно
 
Теперь разделим обе части равенства <tex> (*) </tex> на <tex> w(i)w(j) </tex>. Получим, что расстояние между целевыми функциями равно
  
<tex dpi = 150> -\frac{p(j)}{w(j)} = -\frac{1}{q(j)} </tex>
+
<tex> -\dfrac{p(j)}{w(j)} = -\dfrac{1}{q(j)} </tex>
  
 
Это расстояние минимально (по модулю), так как мы выбирали работу <tex> j </tex> с максимальным значением <tex> q(j) </tex>. Из этих утверждений и следует оптимальность построенного алгоритмом расписания.  
 
Это расстояние минимально (по модулю), так как мы выбирали работу <tex> j </tex> с максимальным значением <tex> q(j) </tex>. Из этих утверждений и следует оптимальность построенного алгоритмом расписания.  
 
}}
 
}}
== Литература ==
+
 
 +
== 1 | intree | Sum(w*C)==
 +
<tex dpi="200"> 1 \mid intree \mid \sum w_i C_i </tex>
 +
{{Задача
 +
|definition=
 +
Необходимо составить расписание на одном станке работ с произвольными временами выполнения. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы [[Дерево, эквивалентные определения | деревом]], в котором листья {{---}} работы, которые доступны в начале, а все остальные работы недоступны пока все их дети не будут выполнены.
 +
}}
 +
Сведем задачу <tex> S_{in} = 1 \mid intree \mid \sum w_i C_i </tex> к решенной задаче <tex>S_{out} = 1 \mid outtree \mid \sum w_i C_i </tex> следующим образом:
 +
# Развернем все ребра: если работа <tex> i </tex> зависела от работы <tex> j </tex>, теперь работа <tex> j </tex> будет зависеть от <tex> i </tex>.
 +
# Заменим все стоимости <tex> w_i </tex> на противоположные <tex> w'_i = - w_i</tex>.
 +
{{Теорема
 +
|statement=Развернутое оптимальное расписание соответствующей задачи <tex> S_{out} </tex> с весами <tex> w'_i </tex> является оптимальным расписанием для задачи  <tex> S_{in} </tex>
 +
|proof=
 +
Полученное расписание будет допустимым, так как расписание для <tex> S_{out} </tex> было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув ребра, мы не могли нарушить это свойство. Также из-за того, что мы развернули ребра в расписании, мы добились того, что все работы выполняются в правильном порядке (в расписании для <tex> S_{out} </tex> из-за того, что все ребра были развернуты, порядок был нарушен для всех работ). Таким образом получили, что расписание допустимое.
 +
 
 +
Пусть с помощью задачи <tex> S_{out} </tex> мы получили последовательность работ <tex> 1 \dots n </tex>. Распишем по определению значение целевой функции для <tex> S_{out} </tex>:
 +
<tex>
 +
\sum\limits_{i=1}^n \left( -w_i C_i \right)
 +
= \sum \limits_{i=1}^n \left( -w_i \sum \limits_{j=1}^i p_j \right) = \\
 +
= \sum\limits_{i=1}^n \left( w_i \sum\limits_{j=i+1}^n p_j \right)
 +
- \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i = \\
 +
= \sum\limits_{i=1}^n \left( w_i \sum\limits_{j=i}^n p_j \right)
 +
- \sum\limits_{i=1}^n w_i p_i
 +
- \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i
 +
</tex>
 +
Заметим, что первое слагаемое соответствует целевой функции <tex> \sum w_i C_i </tex> для последовательности <tex> n \dots 1 </tex>, а второе и третье слагаемые — константы, зависящие только от входных данных и не зависящие от перестановки работ. Таким образом, оптимальное значение для <tex> S_{out} </tex> также минимизирует <tex> S_{in} </tex>.
 +
}}
 +
 
 +
== Источники информации ==
 
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78
 
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78
  
[[Категория: Дискретная математика и алгоритмы]]
+
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Текущая версия на 19:03, 4 сентября 2022

[math]1 \mid outtree \mid \sum w_i C_i[/math]


Задача:
Необходимо составить расписание на одном станке работ с произвольными временами выполнения. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы исходящим деревом — работа, которая соответствует корню, доступна в начале, все другие работы зависят от одной работы — отца в дереве.

Тривиальным примером подобной задачи является демонтаж сложного механизма.

Свойства оптимального расписания

Докажем некоторые свойства оптимального расписания, которые мы будем использовать в доказательстве корректности алгоритма.

Введем некоторые обозначения для удобства. За [math]\mathrm{edges} [/math] обозначим список всех ребёр дерева. Для всех работ [math]i = 1, \ldots, n[/math] обозначим за [math]S(i)[/math] всех потомков [math]i[/math] в дереве зависимостей, включая саму работу [math]i[/math], введём новый параметр работы [math]q_i = \dfrac{w_i}{p_i}[/math].

Для подмножества работ [math]I \subseteq \{1, \ldots, n\}[/math] определим:

[math]w(I) = \sum\limits_{i \in I} w_i, p(I) = \sum\limits_{i \in I} p_i, q(I) = \dfrac{w(I)}{p(I)}[/math]

Два непересекающихся множества работ [math]I, J \subseteq \{1, \ldots, n\}[/math] будем называть параллельными [math](I \sim J)[/math], если для всех [math]i \in I, j \in J[/math] выполняется: [math]i[/math] не является ни предком, ни потомком [math]j[/math]. Если множества состоят из одной работы [math]I = \{i\},\ J = \{j\}[/math], будем писать [math]i \sim j[/math]. Каждое расписание представлено перестановкой [math]\pi[/math].

Лемма:
Пусть [math]\pi[/math] — оптимальное расписание, [math]I[/math] и [math]J[/math] — два таких параллельных блока (множества работ, выполняемых последовательно) из [math]\pi[/math], что [math]J[/math] выполняется сразу после [math]I[/math]. Пусть [math]\pi'[/math] — расписание, полученное из [math]\pi[/math] перестановкой [math]I[/math] и [math]J[/math]. Тогда выполяются следующие пункты:
[math](a)~ I \sim J \Rightarrow q(I) \geqslant q(J)[/math]
[math](b)[/math] Если [math]I \sim J[/math] и [math]q(I) = q(J)[/math], то [math]\pi'[/math] — оптимальное расписание.
Доказательство:
[math]\triangleright[/math]

[math](a)[/math]

Пусть [math]f = \sum w_i C_i[/math]. Так как [math]\pi[/math] — оптимальное расписание, то [math]f(\pi) \leqslant f(\pi')[/math]. Таким образом:
[math]0 \leqslant f(\pi') - f(\pi) = w(I) p(J) - w(J) p(I)[/math]
Поделим на [math]p(I)p(J)[/math]:
[math]q(I) = \dfrac{w(I)}{p(I)} \geqslant \dfrac{w(J)}{p(J)} = q(J) [/math]

[math](b)[/math]

Если [math]q(I) = q(J) [/math], то [math]f(\pi) = f(\pi') [/math], следовательно расписание [math]\pi'[/math] оптимально.
[math]\triangleleft[/math]
Теорема:
Пусть [math]i, ~j[/math] работы такие, что [math]i[/math] — предок [math]j[/math], и [math] q_j = \max \{q_k \mid ~ (i, k) \in \mathrm{edges} \}[/math].
Тогда существует оптимальное расписание, в котором работа [math]j[/math] идёт сразу после работы [math]i[/math]
Доказательство:
[math]\triangleright[/math]

Каждое расписание может быть представлено последовательностью работ в порядке, в котором они выполняются. Пусть [math] \pi [/math] будет оптимальной такой последовательностью. Также предположим, что количество работ между [math] i [/math] и [math] j [/math] равное [math] l [/math] было бы минимальным. Можно считать, что [math] l \gt 0 [/math]. Тогда расписание можно представить следующим образом:

JobBlock.jpg

Рассмотрим [math]2[/math] случая.

Случай 1: [math] k \in S(i) [/math]

Работа [math] j [/math] не является потомком работы [math] k [/math] , иначе у неё было бы [math]2[/math] предка. Следовательно, [math] k \sim j [/math]. По лемме [math] q(k) \geqslant q(j) [/math], а по условию выбора [math] j [/math] имеем [math] q(j) \geqslant q(k) [/math], значит, [math] q(j) = q(k) [/math]. Опять же из леммы следует, что работы [math] k [/math] и [math] j [/math] можно поменять местами, не ухудшив расписание. Это противоречит тому, что мы выбрали минимальное [math] l [/math].

Случай 2: [math] k \not\in S(i) [/math]

Пусть [math] h [/math] будет последней работой в расписании между [math] i [/math] и [math] j\ ( [/math]включая работу [math] i) [/math], которая принадлежит [math] S(i) [/math], то есть для всех работ [math] r [/math] в множестве [math] K [/math], назначенных между [math] h [/math] и [math] j [/math], имеем, что [math] r \not\in S(i) [/math]. Так как наш граф зависимостей работ является исходящим деревом и [math](i, j) \in \mathrm{edges} [/math], то любой предок работы [math] j [/math] также является и предком работы [math] i [/math]. Поэтому никакая работа из [math] K [/math] не является предком [math] j\ ([/math]иначе бы она не смогла стоять после [math] i) [/math] или потомком, значит, [math] K \sim j [/math]. Из этого следует, что [math] q(K) \geqslant q(j) [/math].
Работа [math] h \in S(i) [/math] не является потомком какой-либо работы [math] r \in K [/math]. В противном же случае получалось, что [math] r \in S(i) [/math], значит, [math] h [/math] является не последней работой из [math] S(i) [/math] между [math] i [/math] и [math] j [/math]. Поэтому [math] h \sim K [/math], откуда тут же следует, что [math] q(h) \geqslant q(K) \geqslant q(j) [/math]. По определению [math] j [/math] имеем, что [math] q(j) \geqslant q(h) [/math], следовательно [math] q(j) = q(h) = q(K) [/math]. По лемме мы можем поменять блоки [math] K [/math] и [math] j [/math] не нарушив оптимальности расписания.
Таким образом мы можем менять соседние работы или блоки работ, пока [math] j [/math] не окажется сразу за [math] i [/math].
[math]\triangleleft[/math]

Алгоритм

Доказанная в предыдущем пункте теорема уже даёт основную идею алгоритма: взять работу [math] j [/math], отличную от корня дерева, с максимальным значением [math] q_j [/math] и поставить её в расписании сразу после своего непосредственного предка [math] i [/math]. Так как существует оптимальное расписание, в котором работа [math] j [/math] идёт сразу после [math] i [/math], то мы можем объедить вершины графа в одну вершину [math] J_i = \{i, j\}[/math], которая представляет собой последовательность [math] \pi_i \colon i, j [/math]. Все сыновья работы [math] j [/math] станут сыновьями новой вершины [math] J_i [/math].

Будем повторять процесс слияния вершин, пока не останется всего одна вершина.

Таким образом каждая вершина [math] i [/math] представляется множеством работ [math] J_i [/math] и соответствующей этому множеству последовательностью [math] \pi_i [/math]. На очередном шаге алгоритма мы находим вершину [math] j [/math], отличную от корня, с максимальным значением [math] q_j [/math]. Пусть [math] par [/math] — непосредственный предок работы [math] j [/math]. Тогда нам надо найти такую вершину [math] i [/math], что [math] par \in J_i [/math]. После этого мы объединяем обе вершины, заменяя [math] J_i [/math] и [math] \pi_i [/math] на [math] J_i \cup J_j [/math] и [math] \pi_i \circ \pi_j [/math], где [math] \pi_i \circ \pi_j [/math] — это конкатенация последовательностей [math] \pi_i [/math] и [math] \pi_j [/math].

Детали описаны в алгоритме ниже, в котором

  • [math] E(i) [/math] обозначает последнюю работу в последовательности [math] \pi_i [/math],
  • [math] P(i) [/math] обозначает предка в графе зависимостей, а после слияния с какой-то вершиной [math] j [/math] — предыдущую работу в последовательности [math] \pi_j [/math].
 w[root] = [math] - \infty [/math]
 for i = 1..n
   E[i] = {i} 
   J[i] = {i} 
   q[i] = w[i] \ p[i]
 L = {1, ... , n}
 while L [math] \ne [/math] {root} // пока в списке работ не останется только корень
   Найти работу j [math] \in [/math] L с максимальным значением q[j]
   par = P[j]
   Найти i, что par [math] \in [/math] J[i]
   w[i] += w[j]
   p[i] += p[j]
   q[i] = w[i] / w[j]    // пересчитаем значения в вершине
   P[j] = E[i]           // предком работы j теперь будет последняя работа в [math] \pi_i [/math]
   E[i] = E[j]           // последней работой в [math] \pi_i [/math] теперь будет последняя работа в [math] \pi_j [/math]
   J[i] = J[i] [math] \cup [/math] J[j]
   L = L \ {j}

Вначале делаем присваивание [math] w(root) = -\infty [/math], чтобы корень никогда не выбрался на шаге выбора вершины с максимальным значением [math] q [/math]. В реализации же можно просто дополнительно проверять на равенство с корнем, чтобы избежать переполнений или испортить значение [math]-\infty[/math].

После завершения этой процедуры оптимальное расписание можно восстановить с конца, зная [math] E(root) [/math] и массив [math] P [/math].

Если для получения работы [math] j [/math] с минимальным значением [math] q(j) [/math] использовать очередь с приоритетами, а для поиска родителям вершины использовать систему непересекающихся множеств, то время работы алгоритма будет [math] \mathcal{O}(n\log{n}) [/math].

Проиллюстрируем работу алгоритма на следующем примере.

JobsOuttrees.jpg

Первой выберется работа с номером [math] 5 [/math]. Она объединится со своим родителем [math] 2 [/math] и допишется в конец [math] \pi_2 [/math]. Потом выберется работа [math] 4 [/math], потом [math] \{2, 5\} [/math] и т. д. Процесс будет продолжаться, пока не останется одна вершина. Ответ — оптимальная последовательность работ — содержится в [math] \pi_1 [/math], который написан внутри последней вершины.

Доказательство оптимальности алгоритма

Теорема:
Алгоритм [math] 1 \mid outtree \mid \sum w_i C_i[/math] строит оптимальное расписание.
Доказательство:
[math]\triangleright[/math]

Доказательство проведём по индукции. Очевидно, что для одной вершины алгоритм построит оптимальное расписание. Пусть теперь он может составить оптимальную последовательность назначенных работ числом меньше [math] n [/math]. Пусть также работы [math] i, j [/math] — работы, которые объединятся на первом шаге алгоритма. Тогда оптимальное расписание [math] R [/math] можно представить следующим образом:

[math] \pi \colon \pi (1), \ldots, \pi (k), i, j, \pi (k + 3), \ldots, \pi (n) [/math]

После объединения работ [math] i [/math] и [math] j [/math] в одну расписание [math] R' [/math] примет такой вид:

[math] \pi ' \colon \pi (1), \ldots, \pi (k), I, \pi (k + 3), \ldots, \pi (n) [/math]

где [math] I = \{i, j\}, ~w(I) = w(i) + w(j), p(I) = p(i) + p(j)[/math]. Обозначим за [math] f_n(\pi ), ~f_{n-1}(\pi ') [/math] целевые функции для последовательностей [math] \pi [/math] и [math] \pi ' [/math] соответственно. Тогда

[math] f_n(\pi ) - f_{n-1}(\pi') = w(i)p(i) + w(j)(p(i) + p(j)) - (w(i) + w(j))(p(i) + p(j)) = -w(i) p(j)\ (*) [/math]

Следовательно, расписание [math] R [/math] будет оптимальным тогда и только тогда, когда расписание [math] R' [/math] будет оптимальным. А по предположению индукции наш алгоритм составит оптимальное расписание для последовательности [math] \pi ' [/math].

Теперь разделим обе части равенства [math] (*) [/math] на [math] w(i)w(j) [/math]. Получим, что расстояние между целевыми функциями равно

[math] -\dfrac{p(j)}{w(j)} = -\dfrac{1}{q(j)} [/math]

Это расстояние минимально (по модулю), так как мы выбирали работу [math] j [/math] с максимальным значением [math] q(j) [/math]. Из этих утверждений и следует оптимальность построенного алгоритмом расписания.
[math]\triangleleft[/math]

1 | intree | Sum(w*C)

[math] 1 \mid intree \mid \sum w_i C_i [/math]

Задача:
Необходимо составить расписание на одном станке работ с произвольными временами выполнения. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы деревом, в котором листья — работы, которые доступны в начале, а все остальные работы недоступны пока все их дети не будут выполнены.

Сведем задачу [math] S_{in} = 1 \mid intree \mid \sum w_i C_i [/math] к решенной задаче [math]S_{out} = 1 \mid outtree \mid \sum w_i C_i [/math] следующим образом:

  1. Развернем все ребра: если работа [math] i [/math] зависела от работы [math] j [/math], теперь работа [math] j [/math] будет зависеть от [math] i [/math].
  2. Заменим все стоимости [math] w_i [/math] на противоположные [math] w'_i = - w_i[/math].
Теорема:
Развернутое оптимальное расписание соответствующей задачи [math] S_{out} [/math] с весами [math] w'_i [/math] является оптимальным расписанием для задачи [math] S_{in} [/math]
Доказательство:
[math]\triangleright[/math]

Полученное расписание будет допустимым, так как расписание для [math] S_{out} [/math] было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув ребра, мы не могли нарушить это свойство. Также из-за того, что мы развернули ребра в расписании, мы добились того, что все работы выполняются в правильном порядке (в расписании для [math] S_{out} [/math] из-за того, что все ребра были развернуты, порядок был нарушен для всех работ). Таким образом получили, что расписание допустимое.

Пусть с помощью задачи [math] S_{out} [/math] мы получили последовательность работ [math] 1 \dots n [/math]. Распишем по определению значение целевой функции для [math] S_{out} [/math]: [math] \sum\limits_{i=1}^n \left( -w_i C_i \right) = \sum \limits_{i=1}^n \left( -w_i \sum \limits_{j=1}^i p_j \right) = \\ = \sum\limits_{i=1}^n \left( w_i \sum\limits_{j=i+1}^n p_j \right) - \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i = \\ = \sum\limits_{i=1}^n \left( w_i \sum\limits_{j=i}^n p_j \right) - \sum\limits_{i=1}^n w_i p_i - \sum\limits_{i=1}^n w_i \sum \limits_{i=1}^n p_i [/math]

Заметим, что первое слагаемое соответствует целевой функции [math] \sum w_i C_i [/math] для последовательности [math] n \dots 1 [/math], а второе и третье слагаемые — константы, зависящие только от входных данных и не зависящие от перестановки работ. Таким образом, оптимальное значение для [math] S_{out} [/math] также минимизирует [math] S_{in} [/math].
[math]\triangleleft[/math]

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

  • P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78