Изменения
Опечатки
L = {1, ... , n}
'''while''' L <tex> \ne </tex> {root} <font color=darkgreen>// пока в списке работ не останется только корень</font>
Найти работу j <tex> \in </tex> L с маскимальным максимальным значением q[j]
par = P[j]
Найти i, что par <tex> \in </tex> J[i]
[[Файл:JobsOuttrees.jpg|650px]]
Первой выберется работа с номером <tex> 5 </tex>. Она объединиться объединится со своим родителем <tex> 2 </tex> и допишется в конец <tex> \pi_2 </tex>. Потом выберется работа <tex> 4 </tex>, потом <tex> \{2, 5\} </tex> и т. д. Процесс будет продолжаться, пока не останется одна вершина. Ответ {{---}} оптимальная последовательность работ {{---}} содержится в <tex> \pi_1 </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> следующим образом:
|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
[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]
