Изменения

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

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

Если же <tex> n < m </tex>, добавим <tex> m - n </tex> фиктивных работ с номерами <tex> n + 1 \dots m </tex>, построим расписание способом выше и удалим из полученного расписания фиктивные работы.

Минимальное значение <tex> C_{max} </tex> вычисляется за <tex> \mathcal{O}(1) </tex> времени.Построение расписания сводится к заполнению матрицы размером <tex> m \times \max{(m, n)} </tex> и выполняется за <tex> \mathcal{O}(m \dot (m + n)) </tex> времени.

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