251
правка
Изменения
Нет описания правки
==Описание алгоритма==
<tex>M_{1}</tex> {{--- }} первый станок. <tex>M_{2}</tex> {{--- }} второй станок.
Разобьем все работы на четыре множества:
* Расписание <tex>M_{2}</tex>: сначала <tex>I_{21}</tex> в соответсвии с расписанием <tex>S_{21}</tex>. Затем <tex>I_{2}</tex> в произвольном порядке. Затем <tex>I_{12}</tex> в соответсвии с <tex>S_{12}</tex>.
'''Примечание''': во время выполнения <tex>I_{21}</tex> на <tex>M_{1}</tex> или <tex>I_{12}</tex> на <tex>M_{2}</tex> могут возникнуть простои
из-за того, что работа ещё не выполнилась на предыдущем станке.
|proof=
Рассмотрим два случая:
#<tex>T_{1}(I_{12}) + T_{1}(I_{1}) \geqslant T_{2}(I_{21}) </tex>. <br>Тогда <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>. <br>Тогда <tex>M_{2}</tex> работает без прерываний, т.к к моменту завершения выполнения <tex>I_{2}</tex> на <tex> M_{2} </tex> все работы <tex>I_{12}</tex> выполнены на <tex>M_{1}</tex> .
|proof=
[[Файл: j2ni2cmax.jpg|400px|thumb|right|
Рис. 1 {{- --}} Расположение работ.
<br>
В серой области могут быть прерывания.
