Изменения

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

Pintreepi1Lmax

2885 байт добавлено, 22:58, 30 мая 2016
Второй шаг
|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>. * # Работы расставляются в неубывающем порядке срокових дедлайнов.
=== Псевдокод ======= Первый шаг ===Алгоритм изменения сроков: deque = i <tex>\mid</tex> i является листом while deque not empty i = stackНа первом шаге мы релаксируем дедлайны всех работ, кроме листовой, в соответствии с предыдущим пунктом.remove_first() for j * В массиве <tex>\midmathtt d</tex> j является предком iхранятся дедлайны работ. * В массиве <tex>d_{j} = \min(d_{j}, d_mathtt {iparents} - 1)</tex> stack.add_last(j) {{Лемма|statement=Работа с новым сроком <tex>{d'_i---}}массив предков </tex> в расписании не имеет опозданий тогда и только тогда, когда она не имела опозданий с оригинальным сроком <tex>{d_i}i</tex>-й работы.|proof=* В переменной <tex>\Rightarrow mathtt i</tex>: Тхранится номер листа (он один, см.кусловие задачи). '''Deque<texint>{d'_i} \leqslant {d_i}</tex>, значит, если опозданий не было со значениями <tex>{d'_i}' deque = </tex>, их не будет и со значениями <tex>{d_i}\varnothing</tex> deque.push(i) <tex>\Leftarrow </tex>: Пусть у нас были сроки <tex>{d_i}</tex> и мы их заменили на <tex>{d '''while''' '''not'''_i}</tex> в соответствии с приведенным алгоритмомdeque. isEmpty:Пронумеруем вершины от <tex>1</tex> до <tex>n</tex> в соответствии с '''обратнымint''' порядком обхода в алгоритме изменения сроков, причём <tex>d_{i} \leqslant d_{j}</tex>, если <tex>i \leqslant j</tex>= deque. В соответствии с расписанием, время, когда деталь закончит обрабатываться на станке <tex>{C_i}</tex> удовлетворяет неравенству <tex>{C_i} \leqslant {d_i}</tex> для всех <tex>{C_1} \dots {C_n}</tex>. Тогда мы имеем <tex>{C_n} \leqslant {d_n} = {dremoveFirst() '''for''' k '''in'''_n}</tex>. Если для какого-то <tex>1 < r \leqslant n</tex> мы имеем <tex>{C_n} \leqslant {parents[j] d'_n}</tex> для <tex>i [k] = r \dots n </tex> и существует работа <tex>j</tex> из этого промежутка, что вершина с номером <tex>r - 1</tex> является ее родителем, тогда <tex>C_{r-1} \leqslant \min(d_{r-1}d[k],d'_{[j}] -1) = d'_{r-1}</tex>}} === Второй шаг ===На втором этапе алгоритма работы сортируются в неубывающем порядке их дедлайнов. Предполагается, что работы занумерованы в соответствии с предыдущим пунктом, т.е deque. <tex>d_{i} \leqslant d_{j}</tex>, если <tex>i \leqslant j</tex>. В переменной <tex>F</tex> хранится время, когда станок освободится. В массиве <tex>r</tex> хранится информация о максимальном времени завершении обработки родителя. Массив <tex>q</tex> хранит информацию о количестве работ, готовых к исполнению addLast(находящихся в очередиk) в момент времени <tex>t</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> не поменяются. === Доказательство корректности ======= Первый шаг ===={{Лемма|statement=Работа с новым сроком <tex>{d'_i}</tex> в расписании не имеет опозданий тогда и только тогда, когда она не имела опозданий с оригинальным сроком <tex>{d_i}</tex>.|proof=<tex>\Rightarrow </tex>:Т.к. <tex>{d'_i} \leqslant {d_i}</tex>, значит, если опозданий не было со значениями <tex>{d'_i}</tex>, их не будет и со значениями <tex>{d_i}</tex>.
<tex>\Leftarrow </tex>
:Пусть у нас были сроки <tex>{d_i}</tex> и мы их заменили на <tex>{d'_i}</tex> в соответствии с приведенным алгоритмом.
:Пронумеруем вершины от <tex>1</tex> до <tex>n</tex> в соответствии с '''обратным''' порядком обхода в алгоритме изменения сроков, причём <tex>d_{i} \leqslant d_{j}</tex>, если <tex>i \leqslant j</tex>. В соответствии с расписанием, время, когда деталь закончит обрабатываться на станке <tex>{C_i}</tex> удовлетворяет неравенству <tex>{C_i} \leqslant {d_i}</tex> для всех <tex>{C_1} \dots {C_n}</tex>. Тогда мы имеем <tex>{C_n} \leqslant {d_n} = {d'_n}</tex>. Если для какого-то <tex>1 < r \leqslant n</tex> мы имеем <tex>{C_n} \leqslant {d'_n}</tex> для <tex>i = r \dots n </tex> и существует работа <tex>j</tex> из этого промежутка, что вершина с номером <tex>r - 1</tex> является ее родителем, тогда <tex>C_{r-1} \leqslant \min(d_{r-1},d'_{j}-1) = d'_{r-1}</tex>.
}}
 
==== Второй шаг ====
Расписание, сгенерированное этим алгоритмом имеет важное свойство: число заданий в очереди в любой момент времени <tex>t</tex> меньше, чем в момент <tex>t + 1</tex>. Действительно, пусть во время <tex>t</tex> мы выполняем <tex>k</tex> работ, и хотя бы <tex>k + 1 \leqslant m</tex> работ готовы к выполению в момент времени <tex>t + 1</tex>. Но т.к. <tex>k + 1 \leqslant m</tex>, значит каждой из работ предшествовала как минимум одна, поскольку у всех вершин, кроме корней, есть как минимум один предок. Значит, в момент времени <tex>t</tex> исполнялось не менее <tex>k + 1</tex> работ, противоречие.
Если существует такое расписание, в котором ни одна из работ не будет выполнена с опозданием, то тогда это свойство сохранится в построенном данным алгоритмом расписании
|proof=
Предположим, что существует работа из <tex>x_{1} \dots x_{n}</tex> расписания, построенного алгоритмом. В таком случае существует работа, которая опоздала по отношению к измененным срокам. Возьмем наименьшее <tex>i</tex> такое, что <tex>x(i) + 1 > d'_{i}</tex>. Пусть <tex>t < d'_{i}</tex> {{---}} наибольшее из удовлетворяющих условию <tex>j < m \mid </tex>, где <tex> x(j) = t, d'_{j} \leqslant d'_{i}</tex>
Такое <tex>t</tex> существует, потому что иначе <tex>m \cdot d'_{i}</tex> работ <tex>j</tex> с <tex>d'_{j} \leqslant d'_{i}</tex> находятся в очереди до <tex>d'_{i}</tex>. Работа <tex>i</tex> к ним не принадлежит, поскольку <tex>x(i) + 1 > d'_{i}</tex>, а значит, что <tex>m \cdot d'_{i} + 1</tex> должны быть в очереди в момент времени <tex>0 \dots d'_{i}</tex> и ни одна работа не должна опаздывать. Противоречие.
Любая работа <tex>j</tex> с <tex>d'_{j} \leqslant d'_{i} </tex> и <tex> x(j) > t </tex> должна иметь предка, начавшего работать в момент времени <tex>t</tex>. Теперь рассмотрим два случая:
}}
==== Корректность алгоритма ====
{{Теорема
|statement=
Пусть <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>
}}
 
==== Асимптотика ====
# На первом шаге мы посещаем каждую вершину не более двух раз (первый {{---}} когда ищем вершину без родителя, второй {{---}} когда релаксируем дедлайны) за <tex>O(n)</tex> времени.
# Делаем сортировку вершин за <tex>O(n \log n)</tex>, а затем обходим все вершины по разу и считаем время начала выполнения каждой работы, в сумме за <tex>O(n)</tex>.
Итоговая сложность {{---}} <tex>O(n \log n)</tex>
 
==См. также==
*[[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]
*[[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]
==Источники информации==
317
правок

Навигация