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