Изменения
→Доказательство корректности алгоритма
Будем считать, что в начале алгоритма все работы упорядочены, как было сказано ранее: <tex> p_1(0) \ge p_2(0) \ge ... \ge p_n(0) </tex>. Это утверждение не меняется на протяжении всего выполнения алгоритма, для любого момента времени. Получаем: <tex> p_1(t) \ge p_2(t) \ge ... \ge p_n(t) </tex>. Докажем что алгоритм составляет расписание в соответствии с этим свойством. Чтобы доказать этот факт, будем считать что в любой момент времени T нет простоев машин, когда есть хотя бы одна невыполненная работа. Получаем:
<tex> T(s_1 + ... + s_m) = p_1 + p_2 + ... + p_n </tex> или <tex> T = {P_n \over S_nS_m} </tex>
Таким образом необходимая оценка достигается нашим алгоритмом.
