3622
правки
Изменения
Нет описания правки
Работа <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> не нарушив оптимальности расписания.
}}
== Алгоритм ==
Доказанная в предыдущем пункте [[#theorem1 | теорема]] уже даёт основную идею алгоритма: взять работу <tex> j </tex>, отличную от корня дерева, с максимальным значением <tex> q_j </tex> и поставить её в расписании сразу после своего непосредственного предка <tex> i </tex>. Так как существует оптимальное расписание, в котором работа <tex> j </tex> идёт сразу после <tex> i </tex>, то мы можем объедить вершины графа в одну вершину <tex> J_i = \{i, j\}</tex>, которая представляет собой последовательность <tex> \pi_i \colon i, j </tex>. Все сыновья работы <tex> j </tex> станут сыновьями новой вершины <tex> J_i </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>.
== Литература ==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78
