Просмотр исходного текста страницы Opij1Cmax

<tex dpi = "200">O \mid p_{ij} = 1 \mid C_{max}</tex>
{{Задача
|definition = Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать время выполнения всех работ.
}}
==Алгоритм==

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

В случае <tex> n \geqslant m </tex> оптимальное расписание циклическими сдвигами последовательности <tex> 1 \dots n </tex> и выглядит следующим образом:
         '''1     2     3   ... k   k+1 ... n-1 n'''
  '''M_1'''    1     2     3   ... k   k+1 ... n-1 n
  '''M_2'''    n     1     2   ... k-1 k   ... n-2 n-1
  '''.'''      ...   ...   ... ... ... ... ... ... ...
  '''.'''      ...   ...   ... ... ... ... ... ... ...
  '''M_m'''    n-m+2 n-m+3 ... ... ... ... ... n-m n-m+1

Если же <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> времени.

==См. также.==
* [[Методы решения задач теории расписаний]]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]