317
правок
Изменения
→Второй шаг
|definition=Рассмотрим задачу на нахождение расписания:
# У нас есть несколько станков, работающих параллельно. У станков могут быть разные скорости выполнения работ.
# Есть несколько заданий, каждое из которых имеет определенный порядок, который указан в направленном из корней в лист [[Классификация задач#Характеристики работintree|intree-дерева]], которое имеет несколько корней и один лист.
# Любая работа на любом станке выполняется единицу времени.
Требуется минимизировать максимальное опоздание <tex>L_{max} = \max\limits_i \{C_i - d_i\}</tex>.
=== Идея ===
Все работы хранятся в качестве вершин [[Классификация задач#Характеристики работintree|intree-дерева]], состоящем из <tex>n</tex> вершин, нескольких корней и одного листа. В intree-дереве у одной вершины может быть два и более родителей.Решение задачи состоит из двух шагов: на первом шаге мы меняем сроки выполнения # Меняем делайны работ в соответствии с их очередностью: для всех <tex>i, j</tex> таких, что существует ребро из <tex>i</tex> в <tex>j</tex> будем менять <tex>{d_i}</tex> на <tex>\min ({d_i}, {d_j} - 1) </tex>. # Работы расставляются в неубывающем порядке их дедлайнов.
=== Псевдокод ===
==== Первый шаг ====
==== Второй шаг ====
На втором этапе алгоритма работы сортируются в неубывающем порядке их дедлайнов. Предполагается, что работы будут занумерованы в соответствии с предыдущим пунктомтак, т.е. что <tex>d_{i} \leqslant d_{j}</tex>, если <tex>i \leqslant j</tex>.* В переменной <tex>\mathtt F</tex> хранится время, когда какой-либо станок освободится.
* В массиве <tex>\mathtt r</tex> хранится информация о максимальном времени завершении обработки родителя.
* Массив <tex>\mathtt q</tex> хранит информацию о количестве работ, готовых к исполнению (находящихся в очереди) в момент времени <tex>t</tex>.
* Массив <tex>\mathtt x</tex> хранит информацию о начале выполнения работы <tex>i</tex>.
* В массиве <tex>\mathtt {child}</tex> хранится индекс ребенка <tex>i</tex>-й работы.
F = 0
'''for''' '''int''' i = 1 .. n
r[i] = 0
'''for''' '''int''' t = 0 .. n
q[t] = 0
'''for''' '''int''' i = 1 .. n '''int''' t = max(r[i], F)
x[i] = t
q[t] = q[t] + 1
'''if''' q[t] == m
F = t + 1
'''int''' j = child[i.child()]
r[j] = max(r[j], t + 1)
В результате ответ можно получить, зная конечный массив <tex>\mathtt x</tex> и делайны работ: <tex>L_{max} = \max\limits_i (\mathtt x[i] + 1 - d_{i}</tex>), так как все работы выполняются единицу времени, следовательно, <tex>C_{i} = \mathtt x[i] + 1</tex>. Можно заметить, что при вычислении ответа неважно, какие дедлайны использовать, начальные или релаксированные, потому что для любого <tex>k</tex> и его предка <tex>i</tex> либо производится релаксация и выполняется равенство <tex> d_{k} = d_{i} - 1</tex>, а значит, после релаксации максимум не изменится, поскольку при замене дедлайна на меньший максимум увеличится, а новое значение <tex>L_{k}</tex> будет равно <tex>L_{i}</tex>, либо мы не делали релаксацию, и значение <tex>d_{k}</tex>, и, следовательно, <tex>L_{k}</tex> не поменяются.
=== Доказательство корректности ===
==== Асимптотика ====
# На перов первом шаге мы посещаем каждую вершину ровно два раза не более двух раз (первый {{---}} когда ищем вершину без родителя, второй {{---}} когда релаксируем дедлайны) за <tex>O(n)</tex> времени.# Делаем сортировку вершин за <tex>O(n \log n)</tex>, а затем для каждой обходим все вершины по разу и считаем время начала выполнения каждой работы, в сумме за линейное время<tex>O(n)</tex>.
Итоговая сложность {{---}} <tex>O(n \log n)</tex>
