3622
правки
Изменения
Нет описания правки
== Постановка задачи ==
Мы должны составить расписание с произвольными временами обработки на одном станке. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы исходящим [[Дерево, эквивалентные определения | деревом ]] {{---}} работа, которая соответствует корню, доступна в начале, все другие работы зависят от одной работы {{---}} отца в дереве. Тривиальным примером подобной задачи является демонтаж сложного механизма.
== Свойства оптимального расписания ==
Докажем некоторые свойства оптимального расписания, которые мы будем использовать в доказательстве корректности алгоритма.
Введем некоторые обозначения для удобства. За <tex> 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 = theorem1
|statement = Пусть <tex>i, ~j</tex> работы такие, что <tex>i</tex> {{---}} потомок предок <tex>j</tex>, и <tex> q_j = \max \{q_k \mid ~ (i, k) \in edges \}</tex>. <br>
Тогда существует оптимальное расписание, в котором работа <tex>j</tex> идёт сразу после работы <tex>i</tex>
|proof =
//TODO: картинка i ... k j
Рассмотрим <tex>2 </tex> случая.
'''Случай 1''': <tex> k \in S(i) </tex>
'''Случай 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 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> не нарушив оптимальности расписания.
