1outtreesumwc

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

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

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

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

Алгоритм

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

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

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

Лемма:

Пусть [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] I \sim J \Rightarrow q(I) \ge q(J)[/math] б) Если [math]I \sim J[/math] и [math]q(I) = q(J)[/math], то [math]\pi'[/math] — оптимальное расписание.

Доказательство:

[math]\triangleright[/math]

а) Пусть [math]f = \sum w_i C_i[/math]. Так как [math]\pi[/math] — оптимальное расписание, то [math]f(\pi) \le f(\pi')[/math]. Таким образом: [math]0 \le f(\pi') - f(\pi) = w(I) p(J) - w(J) p(I)[/math] Поделим на [math]p(I)p(J)[/math]: [math]q(I) = w(I) / p(I) \ge w(J) / p(J) = q(J) [/math] б) Если [math]q(I) = q(J) [/math], то [math]f(\pi) = f(\pi') [/math], следовательно расписание [math]\pi'[/math] оптимально.

[math]\triangleleft[/math]

Литература

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