317
правок
Изменения
→Описание алгоритма
=== Первый шаг ===
Алгоритм изменения сроков:
deque = {i <tex>\mid</tex> i является листом} while (deque not empty)
i = stack.remove_first()
for (j <tex>\mid</tex> j является предком i): <tex>d_{j} := \min(d_{j}, d_{i} - 1)</tex>
stack.add_last(j)
Работа с новым сроком <tex>{d'_i}</tex> в расписании не имеет опозданий тогда и только тогда, когда она не имела опозданий с оригинальным сроком <tex>{d_i}</tex>.
|proof=
В одну сторону утверждение очевидно: т.к. <tex>{d'_i} \leq leqslant {d_i}</tex>, значит, если опозданий не было со значениями <tex>{d'_i}</tex>, их не будет и со значениями <tex>{d_i}</tex>.Докажем лемму в другую сторону: пусть у нас были сроки <tex>{d_i}</tex> и мы их заменили на <tex>{d'_i}</tex> в соответствии с приведенным алгоритмом. Пронумеруем вершины от <tex>1</tex> до <tex>n</tex> в соответствии с '''обратным''' порядком обхода в алгоритме изменения сроков. В соответствии с расписанием, время, когда деталь закончит обрабатываться на станке <tex>{C_i}</tex> удовлетворяет неравенству <tex>{C_i} \leq leqslant {d_i}</tex> для всех <tex>{C_1} \dots {C_n}</tex>. Тогда мы имеем <tex>{C_n} \leq leqslant {d_n} = {d'_n}</tex>. Если для какого-то <tex>1 < r \leq leqslant n</tex> мы имеем <tex>{C_n} \leq leqslant {d'_n}</tex> для <tex>i = r \dots n </tex> и существует работа <tex>j</tex> из этого промежутка, что вершина с номером <tex>r - 1</tex> является ее родителем, тогда <tex>C_{r-1} \leq leqslant \min(d_{r-1},d'_{j}-1) = d'_{r-1}</tex>
}}
=== Второй шаг ===
На втором этапе алгоритма работы сортируются в неубывающем порядке их дедлайнов. Предполагается, что работы занумерованы в соответствии с предыдущим пунктом, т.е. <tex>d_{i} \leq leqslant d_{j}</tex>, если <tex>i \leq leqslant j</tex>.
В переменной <tex>F</tex> хранится время, когда станок освободится.
F = 0
for (i = 1..n)
r[i] = 0
for (t = 0..n)
c[t] = 0
for (i = 1..n)
t = max(r[i], F)
x[i] = t
c[t] = c[t] + 1
if (n[t] == m) F = t + 1
j = s[i]
r[j] = max (r[j], t + 1)
Расписание, сгенерированное этим алгоритмом имеет важное свойство: число заданий в очереди в любой момент времени <tex>t</tex> меньше, чем в момент <tex>t + 1</tex>. Действительно, пусть во время <tex>t</tex> мы выполняем <tex>k</tex> работ, и хотя бы <tex>k + 1 \leq leqslant m</tex> работ готовы к выполению в момент времени <tex>t + 1</tex>. Но т.к. <tex>k + 1 \leq 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 x(j) = t, d'_{j} \leq leqslant d'_{i}</tex>Такое <tex>t</tex> существует, потому что иначе <tex>m \cdot d'_{i}</tex> работ <tex>j</tex> с <tex>d'_{j} \leq 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} \leq leqslant d'_{i} </tex> и <tex> x(j) > t </tex> должна иметь предка, начавшего работать в момент времени <tex>t</tex>. Теперь рассмотрим два случая:
'''Первый случай.''' <tex>t = d'_{i} - 1</tex>.
Мы имеем <tex>x(i)>d'_{i}-1 = t</tex>. Таким образом, предок <tex>k</tex> работы <tex>i</tex> должен начать работать во время <tex>t</tex> и закончить в <tex>d'_{i}</tex>. Но т.к. <tex>d'_{k} \leq leqslant d'_{i} - 1 < d'_{i} = x(k) + 1</tex>, работа <tex>k</tex> так же опоздает, однако <tex>i</tex> было выбрано минимальным. Противоречие.
'''Второй случай.''' <tex>t < d'_{i} - 1</tex>.
В этом случае <tex>m</tex> работ <tex>j</tex> таких, что <tex>d'_{j} \leq leqslant d'_{i}</tex> начнут работать в момент времени <tex>t + 1</tex>, каждая из которых имеет как минимум работающего в <tex>t</tex> предка. По структуре дерева все эти предки различны, кроме того, если <tex>k</tex> {{---}} такой предок <tex>j</tex>, тогда <tex>d'_{k} \leq leqslant d'_{j} - 1 < d'_{j} \leq leqslant d'_{i}</tex>, что противоречит выбору <tex>t</tex>
}}
Данный алгоритм корректно решает задачу <tex>P \mid Tree, p_{i} = 1 \mid L_{max}</tex>
|proof=
Пусть <tex>L'_{max}</tex> {{---}} оптимальное значение. В таком случае, существует расписание, удовлетворяющее <tex>\max\limits_i \{C_i - d_i\} \leq leqslant L'_{max}</tex>, что эквивалетно выражению <tex>C_{i} \leq 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>
}}
==Источники информации==
