Изменения

Перейти к: навигация, поиск

J2ni2Cmax

18 байт добавлено, 14:40, 22 июня 2013
Описание алгоритма
==Описание алгоритма==
<tex>M1M_{1}</tex> - первый станок. <tex>M2M_{2}</tex> - второй станок.
Разобьем все работы на четыре множества:
<ol>
<li><tex>I1I_{1}</tex> - множество всех работ, которые должны выполнится только на <tex>M1M_{1}</tex>. </li><li><tex>I2I_{2}</tex> - множество всех работ, которые должны выполнится только на <tex>M2M_{2}</tex>. </li><li><tex>I12I_{12}</tex> - множество всех работ, которые должны выполнится сначала на <tex>M1M_{1}</tex> затем на <tex>M2M_{2}</tex>. </li><li><tex>I21I_{21}</tex> - множество всех работ, которые должны выполнится сначала на <tex>M2M_{2}</tex> затем на <tex>M1M_{1}</tex>. </li>
</ol>
Решим задачу [[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><li>Расписание <tex>M2</tex>:<tex>I21</tex> в соответсвии с расписанием <tex>S21</tex>. Затем <tex>I2</tex> в произвольном порядке. Затем <tex>I12</tex> в соответсвии с <tex>S12</tex>. </li></ol>
==Доказательство корректности алгоритма==
394
правки

Навигация