317
правок
Изменения
Нет описания правки
<tex dpi = "200">P \mid Intreeintree, p_{i} = 1 \mid L_{max}</tex>
{{Задача
|definition=Рассмотрим задачу на нахождение расписания:
# У нас есть несколько станков, работающих параллельно. У станков могут быть разные скорости выполнения работ.
# Есть несколько заданий, каждое из которых имеет определенный порядок, который указан в направленном из корней в лист intree-дереведерева.
# Любая работа на любом станке выполняется единицу времени.
Требуется минимизировать максимальное опоздание <tex>L_{max} = \max\limits_i \{C_i - d_i\}</tex> .
}}
== Описание алгоритма ==
[[Файл:Intree_example.jpg|thumb|Right|Пример Intreeintree-дерева]]
=== Идея ===
Все вершины хранятся в дереве (англ. Intreeintree), которое имеет несколько корней и один лист.
Работы хранятся в дереве, состоящем из <tex>n</tex> вершин с фиктивной нулевой работой, которая является родителем тех вершин, у которых изначально его не было. В intree-дереве у одной вершины может быть два и более родителей.
{{Теорема
|statement=
Данный алгоритм корректно решает задачу <tex>P \mid Intreeintree, p_{i} = 1 \mid L_{max}</tex>
|proof=
Пусть <tex>L'_{max}</tex> {{---}} оптимальное значение. В таком случае, существует расписание, удовлетворяющее <tex>\max\limits_i \{C_i - d_i\} \leqslant L'_{max}</tex>, что эквивалетно выражению <tex>C_{i} \leqslant d_{i} + L'_{max}</tex> для <tex>i = 1 \dots n </tex>. По первой лемме расписание <tex>S</tex>, построенное для сдвинутых дат <tex>d_{i} + L'_{max}</tex> удовлетворяет данным выражениям. Таким образом, оно оптимально. Нетрудно заметить, что <tex>S</tex> идентично расписанию, построенному алгоритмом, т.к. <tex>(d_{i}+L'_{max})' = d'_{i} + L'_{max} </tex> для <tex>i = 1 \dots n </tex>
