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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(Обозначения и Литература)
Строка 5: Строка 5:
 
== Постановка задачи ==
 
== Постановка задачи ==
 
Мы должны составить расписание с произвольными временами обработки на одном станке. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы исходящим деревом {{---}} работа, которая соответствует корню, доступна в начале, все другие работы зависят от одной работы {{---}} отца в дереве. Тривиальным примером подобной задачи является демонтаж сложного механизма.
 
Мы должны составить расписание с произвольными временами обработки на одном станке. Минимизировать нужно взвешенную сумму времен завершения работ. Зависимости между работами заданы исходящим деревом {{---}} работа, которая соответствует корню, доступна в начале, все другие работы зависят от одной работы {{---}} отца в дереве. Тривиальным примером подобной задачи является демонтаж сложного механизма.
 +
 +
== Алгоритм ==
 +
 +
Решение данной задачи было предложено Адольфсоном и Ху<ref>D. Adolphson and T.C. Hu. Optimal linear ordering. SIAM Journal
 +
of Applied Mathematics, 25:403–423, 1973.</ref> в 1973 году.
 +
 +
Докажем некоторые свойства оптимального расписания, которые мы будем использовать в доказательстве корректности алгоритма.
 +
 +
Введем некоторые обозначения для удобства. Обозначим за <tex>S(i)</tex> поддерево работы <tex>i</tex> в дереве зависимостей. Для всех работ <tex>i = 1, ..., n</tex> обозначим <tex>q_i = \frac{w_i}{p_i}</tex>. Для множества работ <tex>I \subset \{1, ..., n\}</tex>:
 +
 +
<tex>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>
 +
 +
== Литература ==
 +
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78
 +
 +
 +
== Примечания ==
 +
<references/>

Версия 16:22, 21 июня 2012


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

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

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

Алгоритм

Решение данной задачи было предложено Адольфсоном и Ху[1] в 1973 году.

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

Введем некоторые обозначения для удобства. Обозначим за [math]S(i)[/math] поддерево работы [math]i[/math] в дереве зависимостей. Для всех работ [math]i = 1, ..., n[/math] обозначим [math]q_i = \frac{w_i}{p_i}[/math]. Для множества работ [math]I \subset \{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]

Литература

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


Примечания

  1. D. Adolphson and T.C. Hu. Optimal linear ordering. SIAM Journal of Applied Mathematics, 25:403–423, 1973.