1632
правки
Изменения
м
rollbackEdits.php mass rollback
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>, который написан внутри последней вершины.
== Доказательство оптимальности алгоритма ==
Доказательство проведём по индукции. Очевидно, что для одной вершины алгоритм построит оптимальное расписание. Пусть теперь он может составить оптимальную последовательность назначенных работ числом меньше <tex> n </tex>. Пусть также работы <tex> i, j </tex> {{---}} работы, которые объединятся на первом шаге алгоритма. Тогда оптимальное расписание <tex> R </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> \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> (*) </tex> на <tex> w(i)w(j) </tex>. Получим, что расстояние между целевыми функциями равно
<tex dpi = 150> -\fracdfrac{p(j)}{w(j)} = -\fracdfrac{1}{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
[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]
