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=
Рассмотрим два случая:
|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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]