Изменения
Опечатки
<tex dpi = "200" >1 \mid outtree \mid \sum w_i C_i</tex> {{В разработкеЗадача|definition=Необходимо составить расписание на одном станке работ с произвольными временами выполнения. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы исходящим [[Дерево, эквивалентные определения | деревом]] {{---}} работа, которая соответствует корню, доступна в начале, все другие работы зависят от одной работы {{---}} отца в дереве. }}Тривиальным примером подобной задачи является демонтаж сложного механизма. == Свойства оптимального расписания == Докажем некоторые свойства оптимального расписания, которые мы будем использовать в доказательстве корректности алгоритма. Введем некоторые обозначения для удобства. За <tex>\mathrm{edges} </tex> обозначим список всех ребёр дерева. Для всех работ <tex>i = 1, \ldots, n</tex> обозначим за <tex>S(i)</tex> всех потомков <tex>i</tex> в дереве зависимостей, включая саму работу <tex>i</tex>, введём новый параметр работы <tex>q_i = \dfrac{w_i}{p_i}</tex>. Для подмножества работ <tex>I \subseteq \{1, \ldots, n\}</tex> определим: <tex>w(I) = \sum\limits_{i \in I} w_i, p(I) = \sum\limits_{i \in I} p_i, q(I) = \dfrac{w(I)}{p(I)}</tex> Два непересекающихся множества работ <tex>I, J \subseteq \{1, \ldots, n\}</tex> будем называть '''параллельными''' <tex>(I \sim J)</tex>, если для всех <tex>i \in I, j \in J</tex> выполняется: <tex>i</tex> не является ни предком, ни потомком <tex>j</tex>. Если множества состоят из одной работы <tex>I = \{i\},\ J = \{j\}</tex>, будем писать <tex>i \sim j</tex>. Каждое расписание представлено перестановкой <tex>\pi</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> :<tex>(b)</tex> Если <tex>I \sim J</tex> и <tex>q(I) = q(J)</tex>, то <tex>\pi'</tex> {{---}} оптимальное расписание.|proof= <tex>(a)</tex> :Пусть <tex>f = \sum w_i C_i</tex>. Так как <tex>\pi</tex> {{---}} оптимальное расписание, то <tex>f(\pi) \leqslant f(\pi')</tex>. Таким образом: :<tex>0 \leqslant f(\pi') - f(\pi) = w(I) p(J) - w(J) p(I)</tex> :Поделим на <tex>p(I)p(J)</tex>: :<tex>q(I) = \dfrac{w(I)}{p(I)} \geqslant \dfrac{w(J)}{p(J)} = q(J) </tex> <tex>(b)</tex> :Если <tex>q(I) = q(J) </tex>, то <tex>f(\pi) = f(\pi') </tex>, следовательно расписание <tex>\pi'</tex> оптимально.}} {{Теорема|id = theorem1|statement = Пусть <tex>i, ~j</tex> работы такие, что <tex>i</tex> {{---}} предок <tex>j</tex>, и <tex> q_j = \max \{q_k \mid ~ (i, k) \in \mathrm{edges}\}</tex>. <br>Тогда существует оптимальное расписание, в котором работа <tex>j</tex> идёт сразу после работы <tex>i</tex>|proof = Каждое расписание может быть представлено последовательностью работ в порядке, в котором они выполняются. Пусть <tex> \pi </tex> будет оптимальной такой последовательностью. Также предположим, что количество работ между <tex> i </tex> и <tex> j </tex> равное <tex> l </tex> было бы минимальным. Можно считать, что <tex> l > 0 </tex>. Тогда расписание можно представить следующим образом: [[Файл:JobBlock.jpg]] Рассмотрим <tex>2</tex> случая. '''Случай 1''': <tex> k \in S(i) </tex> :Работа <tex> j </tex> не является потомком работы <tex> k </tex> , иначе у неё было бы <tex>2</tex> предка. Следовательно, <tex> k \sim j </tex>. По [[#lemma1 | лемме]] <tex> q(k) \geqslant q(j) </tex>, а по условию выбора <tex> j </tex> имеем <tex> q(j) \geqslant q(k) </tex>, значит, <tex> q(j) = q(k) </tex>. Опять же из [[#lemma1 | леммы]] следует, что работы <tex> k </tex> и <tex> j </tex> можно поменять местами, не ухудшив расписание. Это противоречит тому, что мы выбрали минимальное <tex> l </tex>. '''Случай 2''': <tex> k \not\in S(i) </tex>
:Пусть <tex> h </tex> будет последней работой в расписании между <tex> i </tex> и <tex> j\ ( </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 \mathrm{edges} </tex>, то любой предок работы <tex> j </tex> также является и предком работы <tex> i </tex>. Поэтому никакая работа из <tex> K </tex> не является предком <tex> j\ (</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 dpi = "200" >1 q(h) \mid outtree geqslant q(K) \mid geqslant q(j) </tex>. По определению <tex> j </tex> имеем, что <tex> q(j) \sum w_i C_igeqslant 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>.
Будем повторять процесс слияния вершин, пока не останется всего одна вершина.
== 1 | intree | Sum(w*C)==<texdpi="200">w(I) = 1 \mid intree \mid \sum\limits_w_i C_i </tex>{{Задача|definition=Необходимо составить расписание на одном станке работ с произвольными временами выполнения. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы [[Дерево, эквивалентные определения | деревом]], в котором листья {{---}} работы, которые доступны в начале, а все остальные работы недоступны пока все их дети не будут выполнены. }}Сведем задачу <tex> S_{i \in I} = 1 \mid intree \mid \sum w_i, p(I) C_i </tex> к решенной задаче <tex>S_{out} = 1 \mid outtree \mid \sum\limits_{w_i C_i </tex> следующим образом:# Развернем все ребра: если работа <tex> i \in I} p_i</tex> зависела от работы <tex> j </tex>, q(I) теперь работа <tex> j </tex> будет зависеть от <tex> i </tex>.# Заменим все стоимости <tex> w_i </tex> на противоположные <tex> w'_i = - w_i</tex>.{{Теорема|statement= \fracРазвернутое оптимальное расписание соответствующей задачи <tex> S_{out} </tex> с весами <tex> w(I)'_i </tex> является оптимальным расписанием для задачи <tex> S_{in}</tex>|proof=Полученное расписание будет допустимым, так как расписание для <tex> S_{pout} </tex> было допустимым, и в нем никакие две работы не пересекались и не прерывались. Развернув ребра, мы не могли нарушить это свойство. Также из-за того, что мы развернули ребра в расписании, мы добились того, что все работы выполняются в правильном порядке (I)в расписании для <tex> S_{out}</tex>из-за того, что все ребра были развернуты, порядок был нарушен для всех работ). Таким образом получили, что расписание допустимое.
== Литература Источники информации ==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78
[[Категория: Алгоритмы и структуры данных]]== Примечания ==<references/>[[Категория: Теория расписаний]]