3622
правки
Изменения
Нет описания правки
Мы должны составить расписание с произвольными временами обработки на одном станке. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы исходящим деревом {{---}} работа, которая соответствует корню, доступна в начале, все другие работы зависят от одной работы {{---}} отца в дереве. Тривиальным примером подобной задачи является демонтаж сложного механизма.
== Алгоритм Свойства оптимального расписания ==
<texdpi = 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>.
{{Лемма
|id=46lemma1|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>. Тогда выполяются следующие пункты:а) <tex> (a)~ I \sim J \Rightarrow q(I) \ge q(J)</tex> б<tex>(b) </tex> Если <tex>I \sim J</tex> и <tex>q(I) = q(J)</tex>, то <tex>\pi'</tex> {{---}} оптимальное расписание.
|proof=
<tex>0 \le f(\pi') - f(\pi) = w(I) p(J) - w(J) p(I)</tex>
Поделим на <tex>p(I)p(J)</tex>:
<texdpi = 150>q(I) = \frac{w(I) / }{p(I) } \ge \frac{w(J) / }{p(J) } = q(J) </tex>
}}
{{Теорема
|id = theorem1
|statement = Пусть <tex>i, ~j</tex> работы такие, что <tex>i</tex> {{---}} потомок <tex>j</tex>, и <tex> q_j = \max \{q_k \mid ~ (i, k) \in E \}</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>. Тогда расписание можно представить следующим образом:
}}
== Литература ==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78
[[Категория: Дискретная математика и алгоритмы]]== Примечания ==<references/>[[Категория: Теория расписаний]]
