24
правки
Изменения
Добавлен конспект
<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} \ge n </tex>.
# В допустимом расписании каждую работу нужно обработать на всех станках, причем ее нельзя обрабатывать на двух станках одновременно, поэтому <tex> T_{min} \ge m </tex>.
Тогда <tex> T_{min} = \max{(m, n)} </tex>.
В случае <tex> n \ge 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> O(1) </tex> времени.
Построение расписания сводится к заполнению матрицы размером <tex> m \times \max{(m, n)} </tex> и выполняется за <tex> O(m \dot (m + n)) </tex> времени.
==См. также.==
* [[Методы решения задач теории расписаний]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
{{Задача
|definition = Дано <tex>m</tex> одинаковых станков, которые работают параллельно и <tex>n</tex> работ, котороые необходимо выполнить в произвольном порядке на всех станках. Время выполнения каждой работы на любом станке одинаково и равно 1. Необходимо минимизировать время выполнения всех работ.
}}
==Алгоритм==
===Описание алгоритма===
Минимальное значение <tex> T_{min} </tex> минимизуруемой функции упирается в следующие ограничения:
# В допустимом расписании на каждом станке надо обработать каждую работу, поэтому <tex> T_{min} \ge n </tex>.
# В допустимом расписании каждую работу нужно обработать на всех станках, причем ее нельзя обрабатывать на двух станках одновременно, поэтому <tex> T_{min} \ge m </tex>.
Тогда <tex> T_{min} = \max{(m, n)} </tex>.
В случае <tex> n \ge 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> O(1) </tex> времени.
Построение расписания сводится к заполнению матрицы размером <tex> m \times \max{(m, n)} </tex> и выполняется за <tex> O(m \dot (m + n)) </tex> времени.
==См. также.==
* [[Методы решения задач теории расписаний]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
