Изменения
PSumCi
,Нет описания правки
|statement= Алгоритм <tex>P \mid \mid \sum C_{i}</tex> строит оптимальное расписание.
|proof= Пусть это не так и оптимальное расписание отличается от расписания построенного алгоритмом. Заметим что расписание построенное алгоритмом удовлетворяет обеим леммам. Тогда можно воспользоваться одной из них чтобы улучшить оптимальное раписание. Следовательно {{---}} оптимальное расписание не оптимально. Противоречие. }}
=== Источники информации ===
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 26 - 28
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]