394
правки
Изменения
→Описание алгоритма
==Описание алгоритма==
<tex>M1</tex> - первый станок. <tex>M2</tex> - второй станок. Разобьем все работы на четыре множества:<ol><li><tex>I1</tex> - множество всех работ, которые должны выполнится только на <tex>M1</tex>. </li><li><tex>I2</tex> - множество всех работ, которые должны выполнится только на <tex>M2</tex>. </li><li><tex>I12</tex> - множество всех работ, которые должны выполнится сначала на <tex>M1</tex> затем на <tex>M2</tex>. </li><li><tex>I21</tex> - множество всех работ, которые должны выполнится сначала на <tex>M2</tex> затем на <tex>M1</tex>. </li><ul>Режим задачу [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]] для <tex>I12</tex> и для <tex>I21</tex>. Получим расписание <tex>S12</tex> и <tex>S21</tex>.Тогда оптимальное расписание для нашей задачи будет следующим:<ol><li>Расписание <tex>M1</tex>: <tex>I12</tex> в соответсвии с расписанием <tex>S12</tex>. <tex>I1</tex> в произвольном порядке. Затем <tex>I21</tex> в соответсвии с <tex>S21</tex>.<li>Расписание <tex>M2</tex>:<tex>I21</tex> в соответсвии с расписанием <tex>S21</tex>. Затем <tex>I2</tex> в произвольном порядке. Затем <tex>I12</tex> в соответсвии с <tex>S12</tex>.
==Доказательство корректности алгоритма==
