<tex dpi =200>J2 \mid n_i \leqslant 2 \mid C_{max}</tex>{{Задача|definition=Постановка задачи==Рассмотрим задачу:<ol><li>*Дано <tex>n</tex> работ и <tex>2</tex> станка.</li><li>*Для каждой работы известно её время выполнения на каждом станке <tex>p_{ij}</tex>.</li><li>*Для каждой работы известна последовательность <tex>O_{i1}, \ O_{i2} \ ... \ O_{ik}</tex> станков - порядок, в котором нужно выполнить работу. <li>*В каждой последовательности <tex>O_{i}</tex> не более двух элементов.</li></ol>Требуется минимизировать время окончания выполнения всех работ.}}
==Описание алгоритма==
Разобьем все работы на четыре множества:
<ol><li>#<tex>I_{1}</tex> {{- --}} множество всех работ, которые должны выполниться только на <tex>M_{1}</tex>. </li><li>#<tex>I_{2}</tex> {{- --}} множество всех работ, которые должны выполниться только на <tex>M_{2}</tex>. </li><li>#<tex>I_{12}</tex> {{- --}} множество всех работ, которые должны выполниться сначала на <tex>M_{1}</tex> затем на <tex>M_{2}</tex>. </li><li>#<tex>I_{21}</tex> {{--- }} множество всех работ, которые должны выполниться сначала на <tex>M_{2}</tex> затем на <tex>M_{1}</tex>. </li></ol>
Решим задачу [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]] для <tex>I_{12}</tex> и для <tex>I_{21}</tex> независимо. Получим расписание <tex>S_{12}</tex> и <tex>S_{21}</tex>.
Тогда оптимальное расписание для нашей задачи будет следующим:
<ul><li> * Расписание <tex>M_{1}</tex> : сначала <tex>I_{12}</tex> в соответсвии с расписанием <tex>S_{12}</tex>. Затем <tex>I_{1}</tex> в произвольном порядке. Затем <tex>I_{21}</tex> в соответсвии с <tex>S_{21}</tex>. <li> * Расписание <tex>M_{2}</tex> : сначала <tex>I_{21}</tex> в соответсвии с расписанием <tex>S_{21}</tex>. Затем <tex>I_{2}</tex> в произвольном порядке. Затем <tex>I_{12}</tex> в соответсвии с <tex>S_{12}</tex>.</ul>
Примечание: во время выполнения <tex>I_{21}</tex> на <tex>M_{1}</tex> или <tex>I_{12}</tex> на <tex>M_{2}</tex> могут возникнуть простои
==Доказательство корректности алгоритма==
<tex>T_{j}(x)</tex> {{- --}} время выполнения множества работ <tex>x</tex> на станке <tex>j</tex>.
<tex>G_{j}</tex> {{- --}} множество всех работ, которые нужно сделать хотя бы раз на <tex>j</tex>-м станке. (Формально <tex>G_{1} = I_{1} \cup I_{12} \cup I_{21}</tex>)
{{Лемма
|id=lemma1
|proof=
Рассмотрим 2 случая:
<ul><li>*<tex>T_{1}(I_{12}) + T_{1}(I_{1}) \ge geqslant T_{2}(I_{21}) </tex>. Тогда <tex>M_{1}</tex> работает без прерываний, т.к к моменту завершения выполнения <tex>I_{1}</tex> на <tex> M_{1} </tex> все работы <tex>I_{21}</tex> выполнены на <tex>M_{2}</tex>. *Иначе <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>.
<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> .
</ul>
}}
Рассмотрим станок на котором достигается <tex>C_{max}</tex> .
<ul><li>*Если это <tex>M_{1}</tex>, то оптимальность очевидна (<tex>C_{max} \ge geqslant \sum\limits_{i \in G_{1}} p_{i1} </tex>). <li>*Иначе <tex>C_{max}</tex> достигается на <tex>M_{2}</tex>.
Тогда либо <tex>M_{2}</tex> работает без прерываний и оптимальность очевидна.
Или есть прерывания.
Тогда целевая функция равна ответу задачи [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]] для работ <tex>I_{21}</tex>, который оптимален.
</ul>
}}
