Изменения

Перейти к: навигация, поиск

Pintreepi1Lmax

18 байт добавлено, 17:04, 30 мая 2016
Нет описания правки
|definition=Рассмотрим задачу на нахождение расписания:
# У нас есть несколько станков, работающих параллельно. У станков могут быть разные скорости выполнения работ.
# Есть несколько заданий, каждое из которых имеет определенный порядок, который указан в направленном из корней в лист [[Классификация задач#intree|intree-дерева]], которое имеет несколько корней и один лист.
# Любая работа на любом станке выполняется единицу времени.
Требуется минимизировать максимальное опоздание <tex>L_{max} = \max\limits_i \{C_i - d_i\}</tex>.
=== Идея ===
Все работы хранятся в качестве вершин [[Классификация задач#Зависимость между работами|intree-дерева]], состоящем из <tex>n</tex> вершин, нескольких корней и одного листа. В intree-дереве у одной вершины может быть два и более родителей.
Решение задачи состоит из двух шагов:
317
правок

Навигация