Изменения

Минимальное значение <tex> T_C_{minmax} </tex> минимизуруемой функции упирается в следующие ограничения:# В допустимом расписании на каждом станке надо обработать каждую работу, поэтому <tex> T_C_{minmax} \geqslant n </tex>.# В допустимом расписании каждую работу нужно обработать на всех станках, причем ее нельзя обрабатывать на двух станках одновременно, поэтому <tex> T_C_{minmax} \geqslant m </tex>.Тогда <tex> T_C_{minmax} = \max{(m, n)} </tex>.

В случае <tex> n \geqslant m </tex> оптимальное расписание строится циклическими сдвигами последовательности <tex> 1 \dots n </tex> и выглядит следующим образом: '''{| class="wikitable"|-! !| 1 || 2 || 3 ... k k+1 ... ||<tex>\hdots</tex>|| n-1 || n''' '''|- style="text-align:center;"!<tex>M_1''' </tex>|| 1 || 2 || 3 ... k k+1 ... ||<tex>\hdots</tex>|| n-1 || n '''|- style="text-align:center;"!<tex>M_2''' </tex>|| n || 1 || 2 ||<tex>\hdots</tex>|| n - 2 ... k|| n - 1|- style="text-align:center;"!<tex>M_3</tex>|| n -1 k ... || n || 1 ||<tex>\hdots</tex>|| n - 3 || n-2 n|- style="text-1align:center;" '''.''' ... ... ... ... ... ... ... ... ...!<tex>\vdots</tex> '''.''' ... ... ... ... ... ... ... ... ...||<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex>||<tex>\ddots</tex>||<tex>\vdots</tex>||<tex>\vdots</tex> '''|- style="text-align:center;"!<tex>M_m''' </tex>|| n-m+2 || n-m+3 ... ... ... ... ... || n-m + 4 ||<tex>\hdots</tex>|| n - m ||n-m+1|}

[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]