251
правка
Изменения
Нет описания правки
<table>
<tr>
<td>[[Файл:Figure_5.2.png|500px|thumb|Рис. 1 - . Исходная сеть]]</td><td>[[Файл:Figure_5.9.b.png|500px|thumb|Рис. 2 - . Расширение сети]]</td>
</tr>
</table>
{{Теорема
|statement=Следующие утверждения эквивалентны:
:<tex>(a)</tex> Существует допустимое расписание.
:<tex>(b)</tex> В расширенной сети существует поток от <tex>s</tex> до <tex>t</tex> со значением <tex>\sum\limits_{i=1}^n p_i</tex>.
Рассмотрим в расширенной сети поток величиной <tex>\sum\limits_{i = 1}^n {p_i}</tex>. Обозначим через <tex>x_{iK}</tex> общий поток, который идет от <tex>J_i</tex> до <tex>I_K</tex>. Заметим, что <tex>\sum\limits_{i = 1}^n \sum\limits_{K = 2}^r x_{iK} = \sum\limits_{i = 1}^n p_i</tex>. Достаточно показать, что для каждого подмножества <tex>A \subseteq \{ 1, . . . , n \}</tex> выполняется
Задача <tex>Q \mid pmtn; r_i \mid C_{max}</tex> представляет собой частный случай <tex>Q \mid pmtn; r_i \mid L_{max}</tex>, и может быть решена более эффективно<ref>Описано в Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 133 стр.</ref>.
==Примечания==
<references>
==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 129 {{---}} 133 стр. {{---}} ISBN 978-3-540-69515-8
[[Категория: Теория расписаний]]
