403
правки
Изменения
→Доказательство корректности
Так как мы рассматриваем работы в порядке неубывания их дедлайнов, то, следовательно, <tex> d_{k} \leqslant d_{l} </tex>, и замена работы <tex> k </tex> на <tex> l </tex> в оптимальном расписании <tex> S^* </tex> не может сделать его некорректным. Тогда для доказательства нам осталось показать, что <tex> w_{k} \leqslant w_{l} </tex>.
Пусть <tex> k_{i_{0}} = k </tex> {{---}} работа, замененная работой <tex> i_{0} </tex> в процессе построения <tex> S </tex>, и пусть <tex> k_{i_{1}}, ..., k_{i_{r}} </tex> {{---}} последовательность работ, которые были исключены из <tex> S </tex> после замены <tex> k </tex>, причем работа <tex> k_{i_{v}} </tex> была заменена работой <tex> i_{v} </tex>.
== Время работы ==
