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