3622
правки
Изменения
добавлены теорема, описание алгоритма и псевдокод
Докажем некоторые свойства оптимального расписания, которые мы будем использовать в доказательстве корректности алгоритма.
Введем некоторые обозначения для удобства. За <tex> E edges </tex> обозначим список всех ребёр дерева. Для всех работ <tex>i = 1, ..., n</tex> обозначим обозначим за <tex>S(i)</tex> всех потомков <tex>i</tex> в дереве зависимостей, включая саму работу <tex>i</tex>, введём новый парамерт работы <tex dpi = 150>q_i = \frac{w_i}{p_i}</tex>.
Для подмножества работ <tex>I \subseteq \{1, ..., n\}</tex> определим:
{{Лемма
|id=lemma1
|statement= Пусть <tex>\pi</tex> {{---}} оптимальное расписание, <tex>I</tex> и <tex>J</tex> {{---}} два таких параллельных блока (множества работ, выполняемых последовательно) из <tex>\pi</tex>, что <tex>J</tex> выполняется сразу после <tex>I</tex>. Пусть <tex>\pi'</tex> {{---}} расписание, полученное из <tex>\pi</tex> перестановкой <tex>I</tex> и <tex>J</tex>. Тогда выполяются следующие пункты:
<tex>(a)~ I \sim J \Rightarrow q(I) \geqslant q(J)</tex>
{{Теорема
|id = theorem1
|statement = Пусть <tex>i, ~j</tex> работы такие, что <tex>i</tex> {{---}} потомок <tex>j</tex>, и <tex> q_j = \max \{q_k \mid ~ (i, k) \in E edges \}</tex>. <br>
Тогда существует оптимальное расписание, в котором работа <tex>j</tex> идёт сразу после работы <tex>i</tex>
|proof =
'''Случай 2''': <tex> k \not\in S(i) </tex>
Пусть <tex> h </tex> будет последней работой в расписании между <tex> i </tex> и <tex> j </tex> <tex> ( </tex> включая работу <tex> i) </tex>, которая принадлежит <tex> S(i) </tex>, то есть для всех работ <tex> r </tex> в множестве <tex> K </tex> назначенных между <tex> h </tex> и <tex> j </tex> имеем, что <tex> r \not\in S(i) </tex>. Так как наш граф зависимостей работ является исходящим деревом и <tex>(i, j) \in E edges </tex>, то любой предок работы <tex> j </tex> также является и предком работы <tex> i </tex>. Поэтому никакая работа из <tex> K </tex> не является предком <tex> j </tex> <tex>(</tex>иначе бы она не смогла стоять после <tex> i) </tex> или потомком, значит, <tex> K \sim j </tex>. Из этого следует, что <tex> q(K) \geqslant q(j) </tex>.
Работа <tex> h \in S(i) </tex> не является потомком какой-либо работы <tex> r \in K </tex>. В противном же случае получалось, что <tex> r \in S(i) </tex>, значит, <tex> h </tex> является не последней работой из <tex> S(i) </tex> между <tex> i </tex> и <tex> j </tex>. Поэтому <tex> h \sim K </tex>, откуда тут же следует, что <tex> q(h) \geqslant q(K) \geqslant q(j) </tex>. По определению <tex> j </tex> имеем, что <tex> q(j) \geqslant q(h) </tex>, следовательно <tex> q(j) = q(h) = q(K) </tex>. По [[#lemma1 | лемме]] мы можем поменять блоки <tex> K </tex> и <tex> j </tex> не нарушив оптимальности расписания.
Таким образом каждая вершина <tex> i </tex> представляется множеством работ <tex> J_i </tex> и соответствующей этому множеству последовательностью <tex> \pi_i </tex>. На очередном шаге алгоритма мы находим вершину <tex> j </tex>, отличную от корня, с максимальным значением <tex> q_j </tex>. Пусть <tex> par </tex> {{---}} непосредственный предок работы <tex> j </tex>. Тогда нам надо найти такую вершину <tex> i </tex>, что <tex> par \in J_i </tex>. После этого мы объединяем обе вершины, заменяя <tex> J_i </tex> и <tex> \pi_i </tex> на <tex> J_i \cup J_j </tex> и <tex> \pi_i \circ \pi_j </tex>, где <tex> \pi_i \circ \pi_j </tex> {{---}} это конкатенация последовательностей <tex> \pi_i </tex> и <tex> \pi_j </tex>.
Детали описаны в алгоритме ниже, в котором
* <tex> E(i) </tex> обозначает последнюю работу в последовательности <tex> \pi_i </tex>
* <tex> P(i) </tex> обозначает предка в графе зависимостей, а после слияния с какой-то вершиной <tex> j </tex> {{---}} предыдущую работу в последовательности <tex> \pi_j </tex>.
w[root] = <tex> - \infty </tex>
'''for''' i = 1..n:
E[i] = {i}, J[i] = {i}, q[i] = w[i] \ p[i]
L = {1, ... , n}
'''while''' L <tex> \ne </tex> {root}: // пока в списке работ не останется только корень
Найти работу j <tex> \in </tex> L с маскимальным значением q[j]
par = P[j]
Найти i, что par <tex> \in </tex> J[i]
w[i] += w[j]
p[i] += p[j]
q[i] = w[i] / w[j] // пересчитаем значения в вершине
P[j] = E[i] // предком работы j теперь будет последняя работа в <tex> \pi_i </tex>
E[i] = E[j] // последней работой в <tex> \pi_i </tex> теперь будет последняя работа в <tex> \pi_j </tex>
J[i] = J[i] <tex> \cup </tex> J[j]
L = L \ {j}
Вначале делаем присваивание <tex> w(root) = -\infty </tex>, чтобы корень никогда не выбрался на шаге выбора вершины с максимальным значением <tex> q </tex>. В реализации же можно просто дополнительно проверять на равенство с корнем, чтобы избежать переполнений или испортить значение <tex>-\infty</tex>.
После завершения этой процедуры оптимальное расписание можно восстановить с конца, зная <tex> E(root) </tex> и массив <tex> P </tex>.
Если для получения работы <tex> j </tex> с минимальным значением <tex> q(j) </tex> использовать очередь с приоритетами, а для поиска родителям вершины использовать систему непересекающихся множеств, то время работы алгоритма будет <tex> O(n\log{n}) </tex>.
== Литература ==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78
