1outtreesumwc — различия между версиями
Shersh (обсуждение | вклад) |
Shersh (обсуждение | вклад) |
||
Строка 16: | Строка 16: | ||
<tex dpi = 150>w(I) = \sum\limits_{i \in I} w_i, p(I) = \sum\limits_{i \in I} p_i, q(I) = \frac{w(I)}{p(I)}</tex> | <tex dpi = 150>w(I) = \sum\limits_{i \in I} w_i, p(I) = \sum\limits_{i \in I} p_i, q(I) = \frac{w(I)}{p(I)}</tex> | ||
− | Два непересекающихся множества работ <tex>I, J \subseteq \{1, ..., n\}</tex> будем называть ''параллельными'' | + | Два непересекающихся множества работ <tex>I, J \subseteq \{1, ..., 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>. |
{{Лемма | {{Лемма | ||
Строка 22: | Строка 22: | ||
|about=1 | |about=1 | ||
|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>. Тогда выполяются следующие пункты: | |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) \ | + | <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> {{---}} оптимальное расписание. | <tex>(b)</tex> Если <tex>I \sim J</tex> и <tex>q(I) = q(J)</tex>, то <tex>\pi'</tex> {{---}} оптимальное расписание. | ||
|proof= | |proof= | ||
− | <tex>(a)</tex> Пусть <tex>f = \sum w_i C_i</tex>. Так как <tex>\pi</tex> {{---}} оптимальное расписание, то <tex>f(\pi) \ | + | <tex>(a)</tex> Пусть <tex>f = \sum w_i C_i</tex>. Так как <tex>\pi</tex> {{---}} оптимальное расписание, то <tex>f(\pi) \leqslant f(\pi')</tex>. Таким образом: |
− | <tex>0 \ | + | <tex>0 \leqslant f(\pi') - f(\pi) = w(I) p(J) - w(J) p(I)</tex> |
Поделим на <tex>p(I)p(J)</tex>: | Поделим на <tex>p(I)p(J)</tex>: | ||
− | <tex dpi = 150>q(I) = \frac{w(I)}{p(I)} \ | + | <tex dpi = 150>q(I) = \frac{w(I)}{p(I)} \geqslant \frac{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> оптимально. | <tex>(b)</tex> Если <tex>q(I) = q(J) </tex>, то <tex>f(\pi) = f(\pi') </tex>, следовательно расписание <tex>\pi'</tex> оптимально. | ||
Строка 49: | Строка 49: | ||
'''Случай 1''': <tex> k \in S(i) </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) \ | + | Работа <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> ( </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 </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> не нарушив оптимальности расписания. | ||
}} | }} | ||
== Литература == | == Литература == |
Версия 16:06, 10 июня 2013
Постановка задачи
Мы должны составить расписание с произвольными временами обработки на одном станке. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы исходящим деревом — работа, которая соответствует корню, доступна в начале, все другие работы зависят от одной работы — отца в дереве. Тривиальным примером подобной задачи является демонтаж сложного механизма.
Свойства оптимального расписания
Докажем некоторые свойства оптимального расписания, которые мы будем использовать в доказательстве корректности алгоритма.
Введем некоторые обозначения для удобства. За
обозначим список всех ребёр дерева. Для всех работ обозначим обозначим за всех потомков в дереве зависимостей, включая саму работу , введём новый парамерт работы .Для подмножества работ
определим:
Два непересекающихся множества работ
будем называть параллельными , если для всех выполняется: не является ни предком, ни потомком . Если множества состоят из одной работы , будем писать . Каждое расписание представлено перестановкой .Лемма (1): |
Пусть — оптимальное расписание, и — два таких параллельных блока (множества работ, выполняемых последовательно) из , что выполняется сразу после . Пусть — расписание, полученное из перестановкой и . Тогда выполяются следующие пункты:
Если и , то — оптимальное расписание. |
Доказательство: |
Пусть . Так как — оптимальное расписание, то . Таким образом:
Поделим на :Если , то , следовательно расписание оптимально. |
Теорема: |
Пусть работы такие, что — потомок , и . Тогда существует оптимальное расписание, в котором работа идёт сразу после работы |
Доказательство: |
Каждое расписание может быть представлено последовательностью работ в порядке, в котором они выполняются. Пусть будет оптимальной такой последовательностью со свойством, что количество работ между и равное было бы минимальным. Можно считать, что . Тогда расписание можно представить следующим образом://TODO: картинка i ... k j Рассмотрим 2 случая. Случай 1: Работа лемме , а по условию выбора имеем , значит, . Опять же из леммы следует, что работы и можно поменять местами, не ухудшив расписание. Это противоречит тому, что мы выбрали минимальное . не является потомком работы , иначе у неё было бы предка. Следовательно, . ПоСлучай 2: Работа Пусть будет последней работой в расписании между и включая работу , которая принадлежит , то есть для всех работ в множестве назначенных между и имеем, что . Так как наш граф зависимостей работ является исходящим деревом и , то любой предок работы также является и предком работы . Поэтому никакая работа из не является предком иначе бы она не смогла стоять после или потомком, значит, . Из этого следует, что . не является потомком какой-либо работы . В противном же случае получалось, что , значит, является не последней работой из между и . Поэтому , откуда тут же следует, что . По определению имеем, что , следовательно . По лемме мы можем поменять блоки и не нарушив оптимальности расписания. |
Литература
- P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78