24
правки
Изменения
1 | intree | Sum(w*C) - наводим красоту
}}
== Применение алгоритма в задаче с 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
