1outtreesumwc — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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 \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>.
+
Два непересекающихся множества работ <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) \ge q(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> {{---}} оптимальное расписание.
 
<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) \le f(\pi')</tex>. Таким образом:
+
<tex>(a)</tex> Пусть <tex>f = \sum w_i C_i</tex>. Так как <tex>\pi</tex> {{---}} оптимальное расписание, то <tex>f(\pi) \leqslant f(\pi')</tex>. Таким образом:
  
<tex>0 \le f(\pi') - f(\pi) = w(I) p(J) - w(J) p(I)</tex>
+
<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)} \ge \frac{w(J)}{p(J)} = q(J) </tex>  
+
<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) \ge q(j) </tex>, а по условию выбора <tex> j </tex> имеем <tex> q(j) \ge q(k) </tex>, значит, <tex> q(j) = q(k) </tex>. Опять же из [[#lemma1 | леммы]] следует, что работы <tex> k </tex> и <tex> j </tex> можно поменять местами, не ухудшив расписание. Это противоречит тому, что мы выбрали минимальное <tex> l </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> ( </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

Эта статья находится в разработке!

[math]1 \mid outtree \mid \sum w_i C_i[/math]

Постановка задачи

Мы должны составить расписание с произвольными временами обработки на одном станке. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы исходящим деревом — работа, которая соответствует корню, доступна в начале, все другие работы зависят от одной работы — отца в дереве. Тривиальным примером подобной задачи является демонтаж сложного механизма.

Свойства оптимального расписания

Докажем некоторые свойства оптимального расписания, которые мы будем использовать в доказательстве корректности алгоритма.

Введем некоторые обозначения для удобства. За [math] E [/math] обозначим список всех ребёр дерева. Для всех работ [math]i = 1, ..., n[/math] обозначим обозначим за [math]S(i)[/math] всех потомков [math]i[/math] в дереве зависимостей, включая саму работу [math]i[/math], введём новый парамерт работы [math]q_i = \frac{w_i}{p_i}[/math].

Для подмножества работ [math]I \subseteq \{1, ..., n\}[/math] определим:

[math]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)}[/math]

Два непересекающихся множества работ [math]I, J \subseteq \{1, ..., n\}[/math] будем называть параллельными [math](I \sim J)[/math], если для всех [math]i \in I, j \in J[/math] выполняется: [math]i[/math] не является ни предком, ни потомком [math]j[/math]. Если множества состоят из одной работы [math]I = \{i\}, J = \{j\}[/math], будем писать [math]i \sim j[/math]. Каждое расписание представлено перестановкой [math]\pi[/math].

Лемма (1):
Пусть [math]\pi[/math] — оптимальное расписание, [math]I[/math] и [math]J[/math] — два таких параллельных блока (множества работ, выполняемых последовательно) из [math]\pi[/math], что [math]J[/math] выполняется сразу после [math]I[/math]. Пусть [math]\pi'[/math] — расписание, полученное из [math]\pi[/math] перестановкой [math]I[/math] и [math]J[/math]. Тогда выполяются следующие пункты:

[math](a)~ I \sim J \Rightarrow q(I) \geqslant q(J)[/math]

[math](b)[/math] Если [math]I \sim J[/math] и [math]q(I) = q(J)[/math], то [math]\pi'[/math] — оптимальное расписание.
Доказательство:
[math]\triangleright[/math]

[math](a)[/math] Пусть [math]f = \sum w_i C_i[/math]. Так как [math]\pi[/math] — оптимальное расписание, то [math]f(\pi) \leqslant f(\pi')[/math]. Таким образом:

[math]0 \leqslant f(\pi') - f(\pi) = w(I) p(J) - w(J) p(I)[/math]

Поделим на [math]p(I)p(J)[/math]:

[math]q(I) = \frac{w(I)}{p(I)} \geqslant \frac{w(J)}{p(J)} = q(J) [/math]

[math](b)[/math] Если [math]q(I) = q(J) [/math], то [math]f(\pi) = f(\pi') [/math], следовательно расписание [math]\pi'[/math] оптимально.
[math]\triangleleft[/math]
Теорема:
Пусть [math]i, ~j[/math] работы такие, что [math]i[/math] — потомок [math]j[/math], и [math] q_j = \max \{q_k \mid ~ (i, k) \in E \}[/math].
Тогда существует оптимальное расписание, в котором работа [math]j[/math] идёт сразу после работы [math]i[/math]
Доказательство:
[math]\triangleright[/math]

Каждое расписание может быть представлено последовательностью работ в порядке, в котором они выполняются. Пусть [math] \pi [/math] будет оптимальной такой последовательностью со свойством, что количество работ между [math] i [/math] и [math] j [/math] равное [math] l [/math] было бы минимальным. Можно считать, что [math] l \gt 0 [/math]. Тогда расписание можно представить следующим образом:

//TODO: картинка i ... k j

Рассмотрим 2 случая.

Случай 1: [math] k \in S(i) [/math]

Работа [math] j [/math] не является потомком работы [math] k [/math] , иначе у неё было бы [math]2[/math] предка. Следовательно, [math] k \sim j [/math]. По лемме [math] q(k) \geqslant q(j) [/math], а по условию выбора [math] j [/math] имеем [math] q(j) \geqslant q(k) [/math], значит, [math] q(j) = q(k) [/math]. Опять же из леммы следует, что работы [math] k [/math] и [math] j [/math] можно поменять местами, не ухудшив расписание. Это противоречит тому, что мы выбрали минимальное [math] l [/math].

Случай 2: [math] k \not\in S(i) [/math] Пусть [math] h [/math] будет последней работой в расписании между [math] i [/math] и [math] j [/math] [math] ( [/math] включая работу [math] i) [/math], которая принадлежит [math] S(i) [/math], то есть для всех работ [math] r [/math] в множестве [math] K [/math] назначенных между [math] h [/math] и [math] j [/math] имеем, что [math] r \not\in S(i) [/math]. Так как наш граф зависимостей работ является исходящим деревом и [math](i, j) \in E [/math], то любой предок работы [math] j [/math] также является и предком работы [math] i [/math]. Поэтому никакая работа из [math] K [/math] не является предком [math] j [/math] [math]([/math]иначе бы она не смогла стоять после [math] i) [/math] или потомком, значит, [math] K \sim j [/math]. Из этого следует, что [math] q(K) \geqslant q(j) [/math].

Работа [math] h \in S(i) [/math] не является потомком какой-либо работы [math] r \in K [/math]. В противном же случае получалось, что [math] r \in S(i) [/math], значит, [math] h [/math] является не последней работой из [math] S(i) [/math] между [math] i [/math] и [math] j [/math]. Поэтому [math] h \sim K [/math], откуда тут же следует, что [math] q(h) \geqslant q(K) \geqslant q(j) [/math]. По определению [math] j [/math] имеем, что [math] q(j) \geqslant q(h) [/math], следовательно [math] q(j) = q(h) = q(K) [/math]. По лемме мы можем поменять блоки [math] K [/math] и [math] j [/math] не нарушив оптимальности расписания.
[math]\triangleleft[/math]

Литература

  • P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78