QpmtnriLmax

Рис. 1 - Исходная сеть

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

Рассмотрим еще одну задачу на нахождение расписания:

1. Каждое задание имеет своё времени выпуска [math]r_i[/math].
2. Срок завершения(дедлайн) [math]d_i[/math].

Требуется минимизировать опоздание [math]L_i = C_i - d_i[/math]

Алгоритм решения

Рис. 2.1 - Заменённая подсеть

Применим бинарный поиск. Таким образом сведем задачу к поиску потока сети.

Пусть [math] t_1 \lt t_2 \lt ...\lt t_r [/math] упорядоченная последовательности всех значений [math]r_i[/math] и [math]d_i[/math]. Определим [math] I_K := [t_{K-1}, t_K], \ T_K = t_K-t_{K-−1} [/math] для [math] K = 2,..., r [/math].

Расширим сеть, показанную на Рис. 1 следующим образом:

[math]I_K[/math] - произвольный интервал-узел. Обозначим через [math] J_{i_1}, J_{i_2}, . . . , J_{i_s} [/math] набор предшественников узла [math]I_K[/math], тогда замененная нами подсеть(Рис. 2.1) определяется как [math] I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} [/math]. Расширение сети показано на Рис. 2.2.

Cчитаем, что станки индексируются в порядке невозрастания скоростей [math] s_1 \ge s_2 \ge . . . \ge s_m [/math], кроме того [math]s_{m+1} = 0[/math].

Расширенная подсеть строится путем добавления к вершинам [math] I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} [/math] вершин [math](K, 1), (K, 2), . . . (K, m) [/math]. При [math]j = 1,..., m [/math], есть дуги от [math](K, j)[/math] до [math]I_K[/math] с емкостью [math] j(s_j - s_{j+1}) T_K [/math] и для всех [math]ν = 1,. . . , s[/math] и [math]j = 1,. . ., m[/math] существует дуга из [math]J_{i_ν}[/math] в [math](K, J)[/math] с емкостью [math] (s_j - s_{j+1}) T_K [/math].

Для каждого [math]I_K[/math] у нас есть такие расширения. Кроме того, мы сохраняем дуги из [math]s[/math] в [math]J_i[/math] емкостью [math]p_i[/math] и дуги из [math]I_K[/math] в [math]t[/math] емкостью [math]S_mT_K[/math] (Рис. 1).

Теорема:

Следующие свойства эквивалентны: (А) Существует допустимое расписание. (Б) В расширенной сети существует поток от s до t со значением [math]\sum\limits_{i=1}^{n} p_i[/math]

Рис. 2.2 - Расширение сети

Время работы

Работа с максимальным потоком в расширенной сети занимает [math]O (m n^3)[/math] шагов, проверка может быть сделана с такой же скоростью. Для решения [math]Q|pmtn; r_{i}|L_{max}[/math] мы используем бинарный поиск, получается алгоритм со сложностью [math]O (mn^3(log(n) + log (\max\limits_{i=1}^{n} p_i)) [/math], потому как [math]L_{max}[/math], ограничен [math]n \max\limits_{i=1}^{n}p_i[/math], при [math]s_1 = 1[/math].

[math]Q | pmtn; ri | Cmax[/math] представляет собой частный случай [math]Q | pmtn; ri | Lmax[/math], и может быть решена более эффективно. Labetoulle, Lawler, Lenstra, и Rinnooy Kan разработали алгоритм работающий за [math] O(n log(n) + mn) [/math] специально для этого случая.

Утверждение:

Задача [math]Q | pmtn | Lmax[/math] может быть решена за [math] O(n log(n) + mn) [/math] шагов.

[math]\triangleright[/math]

Решение [math]Q | pmtn; ri | Cmax[/math] эквивалентно нахождению наименьшего [math]T \ge 0[/math], такого, что задача с допустимым временным интервалом [math][r_i, T] (i = 1, . . . , n)[/math] имеет решение. С другой стороны, решение [math]Q | pmtn | Lmax[/math] эквивалентно нахождению такого наименьшего [math]T \ge 0[/math], такого, что задача с временным интервалом [math][0, d_i + T][/math] или [math][−T, d_i][/math] имеет решение.

[math]\triangleleft[/math]

Таким образом, задачи [math]Q | pmtn; ri | Cmax[/math] и [math]Q | pmtn | Lmax[/math] симметричны.

Источники

• Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 379 стр. — ISBN 978-3-540-69515-8