Изменения
→Доказательство корректности алгоритма
==Доказательство корректности алгоритма==
<tex>T_{i}(x)</tex> - время выполнения множества работ <tex>x</tex> на станке <tex>i</tex>.
{{Лемма
|id=lemma1
<li>
Иначе <tex>T_{1}(I_{12}) + T_{1}(I_{1}) < T_{2}(I_{21}) </tex>.
Тогда <tex>M_{2}</tex> работает без прерываний, т.к к тому моменту завершения выполнения <tex>I_{2}</tex> на <tex> M_{2} </tex> все работы <tex>I_{12}</tex> выполнены на <tex>M_{1}</tex>.
}}
Корректность алгоритма очевидна.
Докажем оптимальность.
Пусть, для опеределенности <tex>M_{1}</tex> работает без прерываний.Рассмотрим станок на котором достигается <tex>C_{max}</tex> . Если этот станок работает без прерыванийэто <tex>M_{1}</tex>, то оптимальность очевидна(<tex>C_{max} >= \sum p_\limits_{i\in I_{1}\cup I_{12} \cup I_{21}} p_i </tex>)Иначе <tex>C_{max}</tex> достигается на станке который может простаивать. Пусть для определенности это станок
}}
