Расписание, построенное данным алгоритмом, является корректным и оптимальным.
|proof=
Доказательство будем вести от противного.<br/>Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего Корректность алгоритма, и оптимальное расписание <tex>S_{2}</tex>очевидна.<br/>Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>Докажем оптимальность.<br/>Это первый момент, в Рассмотрим станок на котором расписания отличаются, значит в достигается <tex>S_С_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1max}</tex>.<br/>Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможноЕсли этот станок работает без прерываний, потому что время появления этих работ не меньше то оптимальность очевидна(<tex>t_C_{1max}</tex>.= \sum Q<br/>При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на <ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul>Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/>Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.
}}
