Изменения
→Доказательство корректности алгоритма
Таким образом необходимая оценка достигается нашим алгоритмом.
Допустим хотя бы одна машина простаивает, в момент когда есть невыполненные работы, мы имеем следующее неравенство для времен окончания работ на станках <tex>M_1 ... M_m</tex>:
<tex> f_1 \ge f_2 \ge ... \ge f_m </tex>
В этом случае, если <tex> f_i < f_{i+1} </tex> для некоторого <tex> 1 /le i /le m-1 </tex>, Level последней работы выполнявшейся на станке <tex> M_i} </tex> равно <tex> f_i - \varepsilon </tex>. Где <tex> \varepsilon > 0</tex> достаточно мал, и меньше чем Level последней работы на станке <tex> M_{i+1} </tex>. Пришли к противоречию.
PDF - 140
==Пример==
