1632
правки
Изменения
м
*#<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> .
rollbackEdits.php mass rollback
==Описание алгоритма==
<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=
Рассмотрим два случая:
|proof=
[[Файл: j2ni2cmax.jpg|400px|thumb|right|
Рис. 1 {{- --}} Расположение работ.
<br>
В серой области могут быть прерывания.
}}
==Сложность алгоритма==
Время работы алгоритма равно времени работы алгоритма [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]], то есть <tex>O(n\log n)</tex>.
==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 179 {{---}} 180 стр. {{---}} ISBN 978-3-540-69515-8
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
