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).

Теорема:

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

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

[math]\triangleright[/math]

[math](b) \Rightarrow (a)[/math]: Consider a flow with value [math]\sum\limits_{i = 1}^n {p_i}[/math] in the expanded network. Denote by [math]x_{iK}[/math] the total flow which goes from [math]J_i[/math] to [math]I_K[/math]. Then [math]\sum\limits_{i = 1}^n \sum\limits_{K = 2}^r x_{iK} = \sum\limits_{i = 1}^n p_i[/math]. It is sufficient to show that for each subset [math]A \subseteq \{ 1, . . . , n \}[/math] we have [math]\sum\limits_{i \in A} x_{iK} \le T_Kh(A)[/math]. This means that condition (5.8) holds and the processing requirements [math]x_{1K}, . . . , x_{nK}[/math] can be scheduled in [math]I_K[/math] for [math]K = 2, . . . , r[/math]. Consider in the expanded network the subnetwork induced by [math]A[/math] and the corresponding partial flow. The portion of this partial flow which goes through [math](K, j)[/math] is bounded by [math]\min \{ j(s_j − s_{j + 1})T_K, |A|(s_j − s_{j+1})T_K \} = T_K(s_j − s_{j+1}) \min \{ j, |A| \}[/math]. Thus, we have [math]\sum\limits_{i \in A} x_{iK} \ge T_K \sum\limits_{j = 1}^m(s_j − s_{j+1}) \min \{ j, |A| \} = T_Kh(A)[/math]. (5.9) That the equality in (5.9) holds can be seen as follows. If [math]|A| \gt m[/math], we have [math]\sum\limits_{j = 1}^m \min \{ j, |A| \}(s_j - s_{j + 1}) = s_1 - s_2 + 2s_2 - 2s_3 + 3s_3 - 3s_4 + ... + ms_s - ms_{m+1} =\ [/math] [math]S_m = h(A)[/math]. Otherwise [math]\sum\limits_{j = 1} \min \{ j, |A| \}(s_j - s_{j + 1}) = s_1 - s_2 + 2s_2 - 2s_3 + 3s_3 - ... + (|A| - 1)s_{|A| - 1} -\ [/math] [math]\ - (|A| - 1)s_{|A|} + |A|(s_{|A|} - s_{|A| - 1} - ... - s_m + s_m - s_{m + 1}) = S_{|A|} = h(A)[/math]. [math](a) \Rightarrow (b)[/math]: Assume that a feasible schedule exists. For [math]i = 1, ... , n [/math] and [math]K = 2, ..., r[/math] let [math]x_{iK}[/math] be the “amount of work” to be performed on job [math]i[/math] in the interval [math]I_K[/math] according to this feasible schedule. Then for all [math]K = 2, ..., r[/math] and arbitrary sets [math]A \subseteq \{ 1, . . . , n \}[/math], the inequality [math]\sum\limits_{i \in A} x_{iK} \le T_Kh(A)[/math] (5.10) holds. Furthermore, for [math]i = 1, . . . , n[/math] we have [math]p_i = \sum\limits_{K = 2}^r s_{iK}[/math]. It remains to show that it is possible to send [math]x_{iK}[/math] units of flow from [math]J_i[/math] to [math]I_K[/math] [math](i = 1, . . . , n; K = 2, . . . , r)[/math] in the expanded network. A sufficient condition for the existence of such a flow is that for arbitrary [math]A \subseteq \{ 1, . . . , n \}[/math] and [math]K = 2, . . . , r[/math] the value [math]\sum\limits_{i \in A} x_{iK}[/math] is bounded by the value of a minimum cut in the partial network with sources [math]J_i(i \in A)[/math] and sink [math]I_K[/math]. However, this value is [math]T_K\sum\limits_{j = 1}^m \min \{ j, |A| \}(s_j - s_{j+1})[/math] Using (5.10) and the right-hand side of (5.9), we get [math]\sum\limits_{i \in A} x_{iK} \le T_K h(A) = T_K \sum\limits_{j = 1}^m \min \{ j, |A| \}(s_j - s_{j+1})[/math] which is the desired inequality.

[math]\triangleleft[/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