90
правок
Изменения
→Доказательство корректности алгоритма
|proof=
[[Файл:f2cmax_first_fixed.png|400px|thumb|right|Рис. 1]]
Предположим обратное, что не существует оптимального расписания с одиннаковыми перестановками работ на станках. Рассмотрим некоторое оптимальное расписание с максимальным по длине общим префиксом на станках.
}}
|statement= Пусть имеет случайное расписание, в котором работа <tex> j </tex> идет сразу же после работы <tex> i </tex>. Тогда если <tex> \min(p_{j1}, p_{i2}) \leq \min(p_{i1}, p_{j2}) </tex>, то можем поменять местами эти работы без ухудшение целевой функций.
|proof=
[[Файл:f2cmax_fixed.png|400px|thumb|right|Рис. 1 2 - Расположение последовательных работ]]
Пусть <tex> w_{ij} </tex> {{---}} время, прошедшее с начала выполнения работы <tex> i </tex> на первом станке до окончания работы <tex> j </tex> на втором станке.
Рассмотрим возможные случаи расположения работ <tex> i </tex> и <tex> j </tex> (см. Рис. 12)
<ol>
<li>Работа <tex> i </tex> начинается на втором станке сразу же после завершения ее на первом
