1302
правки
Изменения
→Алгоритм
|id=46
|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> \Rightarrow q(I) \qe q(J)</tex>
б) Если <tex>I \sim J</tex> и <tex>q(I) = q(J)</tex>, то <tex>\pi'</tex> тоже оптимальное расписание.
|proof=
а)
б)
}}
== Литература ==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78
