Opij1Cmax

[math]O \mid p_{ij} = 1 \mid C_{max}[/math]

Задача:

Дано [math]m[/math] одинаковых станков, которые работают параллельно и [math]n[/math] работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать время выполнения всех работ.

Алгоритм

Описание алгоритма

Минимальное значение [math] T_{min} [/math] минимизуруемой функции упирается в следующие ограничения:

1. В допустимом расписании на каждом станке надо обработать каждую работу, поэтому [math] T_{min} \geqslant n [/math].
2. В допустимом расписании каждую работу нужно обработать на всех станках, причем ее нельзя обрабатывать на двух станках одновременно, поэтому [math] T_{min} \geqslant m [/math].

Тогда [math] T_{min} = \max{(m, n)} [/math].

В случае [math] n \geqslant m [/math] оптимальное расписание циклическими сдвигами последовательности [math] 1 \dots n [/math] и выглядит следующим образом:

        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

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

Оценка сложности алгоритма

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

См. также.

• Методы решения задач теории расписаний