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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Время работы)
(Корректность и оптимальность алгоритма)
(не показано 48 промежуточных версий 7 участников)
Строка 1: Строка 1:
<includeonly>[[Категория: В разработке]]</includeonly>
+
<tex dpi = "200">Q \mid pmtn, r_i \mid L_{max}</tex>
 
+
{{Задача
[[Файл:Figure_5.2.png|400px|thumb|right|Рис. 1 - Исходная сеть]]
+
|definition=Рассмотрим задачу на нахождение расписания:
 
+
# У нас есть несколько станков, работающих параллельно. У станков могут быть разные скорости выполнения работ.
==Постановка задачи==
+
# Есть несколько заданий, каждое имеет своё время появления <tex>r_i</tex> и время окончания <tex>d_i</tex>.
Рассмотрим еще одну задачу на нахождение расписания:
+
# Работа может быть прервана в любой момент и продолжена позже на любой машине.
 +
Требуется минимизировать максимальное опоздание <tex>L_{max} = \max\limits_i \{C_i - d_i\}</tex>.
 +
}}
  
# Каждое задание имеет своё времени выпуска <tex>r_i</tex>.
+
==Алгоритм==
# Срок завершения (дедлайн) <tex>d_i</tex>.
+
===Алгоритм решения===
 +
<table>
 +
<tr>
 +
<td>[[Файл:Figure_5.2.png|500px|thumb|Рис. 1. Исходная сеть]]</td>
 +
<td>[[Файл:Figure_5.9.b.png|500px|thumb|Рис. 2. Расширение сети]]</td>
 +
</tr>
 +
</table>
  
Требуется минимизировать опоздание <tex>L_i = C_i - d_i</tex>
 
  
==Алгоритм решения==
+
Как в [[PpmtnriLmax|задаче]] <tex>P \mid pmtn, r_i \mid L_{max}</tex> применим метод [[Вещественный_двоичный_поиск|двоичного поиска]] и сведем задачу к <tex> Q \mid pmtn, r_i, d_i \mid - </tex>. Для существования расписания с <tex> L_{max} \leqslant L^* </tex> требуется, чтобы у работы с номером <tex> i </tex> выполнялось <tex> C_i - d_i \leqslant L^* </tex>, что эквивалентно <tex> C_i \leqslant d_i + L^* </tex>. Опишем алгоритм решения <tex> Q \mid pmtn, r_i, d_i \mid - </tex> при помощи сведения к задаче поиска [[Определение_сети,_потока|максимального потока]].
[[Файл:Figure_5.9.a.png|200px|thumb|right|Рис. 2.1 - Заменённая подсеть]]
 
  
Как в задаче <tex>P|pmtn, r_i|L_{max}</tex> сведем задачу к поиску потока сети. Также будем использовать бинарный поиск.
+
Пусть <tex> t_1 \leqslant t_2 \leqslant ... \leqslant t_r </tex> {{---}} упорядоченная последовательность всех значений <tex>r_i</tex> и <tex>d_i + L^*</tex>.
 +
Определим интервалы на исходной сети (Рис. 1) <tex> I_K := [t_{K-1}, t_K], \  T_K = t_K-t_{K-−1} </tex> для <tex> K = 2,..., r </tex>. Cчитаем, что станки занумерованы в порядке невозрастания скоростей <tex> s_1 \geqslant s_2 \geqslant . . . \geqslant s_m </tex> (также считаем <tex>s_{m+1} = 0</tex>).
  
Пусть <tex> t_1 < t_2 <...< t_r </tex> упорядоченная последовательность всех значений <tex>r_i</tex> и <tex>d_i</tex>.
+
Искомая сеть строится с помощью расширения сети из задачи <tex>P \mid pmtn, r_i \mid L_{max}</tex>. Обозначим через <tex> J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex> набор предшественников узла <tex>I_K</tex>, тогда замененная нами подсеть определяется как <tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex>.
Определим произвольный интервал-узел на исходной сети (Рис. 1) <tex> I_K := [t_{K-1}, t_K], \  T_K = t_K-t_{K-−1} </tex> для <tex> K = 2,..., r </tex>.
 
  
Расширим эту сеть, следующим образом:
+
Расширение сети показано на Рис. 2.
  
Обозначим через <tex> J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex> набор предшественников узла <tex>I_K</tex>, тогда замененная нами подсеть (Рис. 2.1) определяется как <tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex>. Расширение сети показано на Рис. 2.2.
+
Расширенная подсеть строится путем добавления к вершинам <tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex> вершин <tex>(K, 1), (K, 2), . . . (K, m) </tex>. При <tex>j = 1,..., m </tex>, есть дуги от <tex>(K, j)</tex> до <tex>I_K</tex> с пропускной способностью <tex> j(s_j - s_{j+1}) T_K </tex> и для всех <tex>\nu = 1,. . . , s</tex> и <tex>j = 1,. . ., m</tex> существует дуга из <tex>J_{i_\nu}</tex> в <tex>(K, J)</tex> с пропускной способностью <tex> (s_j - s_{j+1}) T_K </tex>. Это выполняется для каждой вершины <tex>I_K</tex>. Кроме того, мы сохраняем дуги из <tex>s</tex> в <tex>J_i</tex> пропускной способностью <tex>p_i</tex> и дуги из <tex>I_K</tex> в <tex>t</tex> пропускной способностью <tex>S_mT_K</tex> (Рис. 1).
 
 
Cчитаем, что станки индексируются в порядке невозрастания скоростей <tex> s_1 \ge s_2 \ge . . . \ge s_m </tex>, кроме того <tex>s_{m+1} = 0</tex>.
 
 
 
Расширенная подсеть строится путем добавления к вершинам <tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex> вершин <tex>(K, 1), (K, 2), . . . (K, m) </tex>. При <tex>j = 1,..., m </tex>, есть дуги от <tex>(K, j)</tex> до <tex>I_K</tex> с емкостью <tex> j(s_j - s_{j+1}) T_K </tex> и для всех <tex>\nu = 1,. . . , s</tex> и <tex>j = 1,. . ., m</tex> существует дуга из <tex>J_{i_\nu}</tex> в <tex>(K, J)</tex> с емкостью <tex> (s_j - s_{j+1}) T_K </tex>.
 
 
 
Для каждой вершины <tex>I_K</tex> существуют вышеуказанные расширения. Кроме того, мы сохраняем дуги из <tex>s</tex> в <tex>J_i</tex> емкостью <tex>p_i</tex> и дуги из <tex>I_K</tex> в <tex>t</tex> емкостью <tex>S_mT_K</tex> (Рис. 1).
 
  
 +
===Корректность и оптимальность алгоритма===
 
{{Теорема
 
{{Теорема
|statement=Следующие свойства эквивалентны:
+
|statement=Следующие утверждения эквивалентны:
 +
:<tex>(a)</tex> Существует допустимое расписание.
 +
:<tex>(b)</tex> В расширенной сети существует поток от <tex>s</tex> до <tex>t</tex> со значением <tex>\sum\limits_{i=1}^n p_i</tex>.
  
(a) Существует допустимое расписание.
+
|proof=<tex>(b) \Rightarrow (a)</tex>
  
(b) В расширенной сети существует поток от <tex>s</tex> до <tex>t</tex> со значением <tex>\sum\limits_{i=1}^n p_i</tex>
+
:Рассмотрим в расширенной сети поток величиной <tex>\sum\limits_{i = 1}^n {p_i}</tex>. Обозначим через <tex>x_{iK}</tex> общий поток, который идет от <tex>J_i</tex> до <tex>I_K</tex>. Заметим, что <tex>\sum\limits_{i = 1}^n \sum\limits_{K = 2}^r x_{iK} = \sum\limits_{i = 1}^n p_i</tex>. Достаточно показать, что для каждого подмножества <tex>A \subseteq \{ 1, . . . , n \}</tex> выполняется
  
|proof=<tex>(b) \Rightarrow (a):</tex>
+
:<tex>\sum\limits_{i \in A} x_{iK} \leqslant T_Kh(A)</tex> ,где <tex>h(A) =  
Рассмотрим в расширенной сети поток величиной <tex>\sum\limits_{i = 1}^n {p_i}</tex>. Обозначим через <tex>x_{iK}</tex> общий поток, который идет от <tex>J_i</tex> до <tex>I_K</tex>. Заметим, что <tex>\sum\limits_{i = 1}^n \sum\limits_{K = 2}^r x_{iK} = \sum\limits_{i = 1}^n p_i</tex>. Достаточно показать, что для каждого подмножества <tex>A \subseteq \{ 1, . . . , n \}</tex> выполняется <tex>\sum\limits_{i \in A} x_{iK} \le T_Kh(A)</tex>.
+
\begin{cases}
 +
S_{|A|}, & \text{if }|A| \leqslant m \\
 +
S_m, & \text{otherwise}
 +
\end{cases} </tex>.
  
Это означает, что условие <tex>\sum\limits_{i \in A} p_i \le Th(A), \forall A \subseteq \{ 1, ... , n \}</tex> выполняется  и требования к обработке <tex>x_{1K}, . . . , x_{nK}</tex> могут быть запланированы как <tex>I_K</tex> для <tex>K = 2, . . . , r</tex>. Рассмотрим подсеть в расширенной сети индуцированной <tex>A</tex> и соответствующие части потока. Фрагмент частичного потока, который проходит через <tex>(K, j)</tex> ограничен
+
:Это означает, что условие <tex>\sum\limits_{i \in A} p_i \leqslant Th(A), \forall A \subseteq \{ 1, ... , n \}</tex> выполняется  и требования к обработке <tex>x_{1K}, . . . , x_{nK}</tex> могут быть запланированы как <tex>I_K</tex> для <tex>K = 2, . . . , r</tex>. Рассмотрим подсеть в расширенной сети в подмножестве <tex>A</tex> и соответствующие части потока. Фрагмент частичного потока, который проходит через <tex>(K, j)</tex> ограничен
  
<tex>\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| \}</tex>.
+
:<tex>\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| \}</tex>.
  
Таким образом, мы имеем
+
:Таким образом, мы имеем
  
<tex>\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)</tex>. (5.9)
+
<table align = center>
 +
<tr>
 +
<td>
 +
<tex>\sum\limits_{i \in A} x_{iK} \geqslant T_K \sum\limits_{j = 1}^m(s_j −- s_{j+1}) \min \{ j, |A| \} = T_Kh(A)</tex>. <tex>(*)</tex>
 +
</td>
 +
</tr>
 +
</table>
  
То, что равенство (5.9) справедливо, может рассматриваться как следствие. Если <tex>|A| > m</tex>, то
+
:То, что равенство <tex>(*)</tex> справедливо, может рассматриваться как следствие. Если <tex>|A| > m</tex>, то
  
<tex>\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} =\ </tex>
+
:<tex>\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} =\ </tex>
<tex>S_m = h(A)</tex>.
+
:<tex>S_m = h(A)</tex>.
  
В противном случае
+
:В противном случае
  
<tex>\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} -\ </tex>
+
:<tex>\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} -\ </tex>
<tex>(|A| - 1)s_{|A|} + |A|(s_{|A|} - s_{|A| - 1} - ... - s_m + s_m - s_{m + 1}) = S_{|A|} = h(A)</tex>.
+
:<tex>(|A| - 1)s_{|A|} + |A|(s_{|A|} - s_{|A| - 1} - ... - s_m + s_m - s_{m + 1}) = S_{|A|} = h(A)</tex>
  
<tex>(a) \Rightarrow (b):</tex>
+
<tex>(a) \Rightarrow (b)</tex><br>
Предположим, что допустимое расписание существует. Для <tex>i = 1, ... , n </tex> и <tex>K = 2, ..., r</tex> пусть <tex>x_{iK}</tex> является "объемом работ", который будет выполняться в интервале <tex>I_K</tex> в соответствии с нашим возможным расписанием. Тогда для всех <tex>K = 2, ..., r</tex> и произвольных наборов <tex>A \subseteq \{ 1, . . . , n \}</tex>, неравенство
+
:Предположим, что допустимое расписание существует. Для <tex>i = 1, ... , n </tex> и <tex>K = 2, ..., r</tex> пусть <tex>x_{iK}</tex> является "объемом работ", который будет выполняться в интервале <tex>I_K</tex> в соответствии с нашим возможным расписанием. Тогда для всех <tex>K = 2, ..., r</tex> и произвольных наборов <tex>A \subseteq \{ 1, . . . , n \}</tex>, неравенство
  
<tex>\sum\limits_{i \in A} x_{iK} \le T_Kh(A)</tex> (5.10)
+
:<table align = center>
 +
<tr>
 +
<td>
 +
<tex>\sum\limits_{i \in A} x_{iK} \leqslant T_Kh(A)</tex> <tex>(**)</tex>
 +
</td>
 +
</tr>
 +
</table>
  
выполняется. Кроме того, для <tex>i = 1, . . . , n</tex> у нас <tex>p_i = \sum\limits_{K = 2}^r s_{iK}</tex>. Остается показать, что можно отправить <tex>x_{iK}</tex> от <tex>J_i</tex> до <tex>I_K</tex> <tex>(i = 1, . . . , n; K = 2, . . . , r)</tex> в расширенной сети. Такой поток существует, если <tex>\forall A \subseteq \{ 1, . . . , n \}</tex> и <tex>K = 2, . . . , r</tex> значение <tex>\sum\limits_{i \in A} x_{iK}</tex> ограничено величиной минимального среза части сети с истоками <tex>J_i(i \in A)</tex> и стоком <tex>I_K</tex>. Тем не менее, это значение
+
выполняется. Кроме того, для <tex>i = 1, . . . , n</tex> у нас <tex>p_i = \sum\limits_{K = 2}^r s_{iK}</tex>. Остается показать, что можно отправить <tex>x_{iK}</tex> от <tex>J_i</tex> до <tex>I_K</tex> <tex>(i = 1, . . . , n; K = 2, . . . , r)</tex> в расширенной сети. Такой поток существует, если <tex>\forall A \subseteq \{ 1, . . . , n \}</tex> и <tex>K = 2, . . . , r</tex> значение <tex>\sum\limits_{i \in A} x_{iK}</tex> ограничено величиной минимального разреза части сети с истоками <tex>J_i(i \in A)</tex> и стоком <tex>I_K</tex>. Тем не менее, это значение
  
 
<tex>T_K\sum\limits_{j = 1}^m \min \{ j, |A| \}(s_j - s_{j+1})</tex>
 
<tex>T_K\sum\limits_{j = 1}^m \min \{ j, |A| \}(s_j - s_{j+1})</tex>
  
Используя (5.10) и правую часть (5.9), получаем
+
Используя <tex>(**)</tex> и правую часть <tex>(*)</tex>, получаем
  
<tex>\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})</tex>
+
<tex>\sum\limits_{i \in A} x_{iK} \leqslant T_K h(A) = T_K \sum\limits_{j = 1}^m \min \{ j, |A| \}(s_j - s_{j+1})</tex>
  
 
что и является искомым неравенством.
 
что и является искомым неравенством.
 
}}
 
}}
[[Файл:Figure_5.9.b.png|500px|thumb|right|Рис. 2.2 - Расширение сети]]
 
  
==Время работы==
+
===Время работы===
  
Работа с максимальным потоком в расширенной сети занимает <tex>O (m n^3)</tex> шагов, проверка может быть сделана с такой же скоростью. Для решения <tex>Q|pmtn; r_{i}|L_{max}</tex> мы используем бинарный поиск, получается алгоритм со сложностью <tex>O (mn^3(log(n) + log (\max\limits_{i=1}^{n} p_i)) </tex>, потому как <tex>L_{max}</tex>, ограничен <tex>n \max\limits_{i=1}^{n}p_i</tex>, при <tex>s_1 = 1</tex>.
+
Работа с максимальным потоком в расширенной сети занимает <tex>O (m n^3)</tex> шагов, проверка может быть сделана с такой же скоростью. Для решения <tex>Q \mid pmtn; r_{i} \mid L_{max}</tex> мы используем бинарный поиск, а значит, получаем алгоритм с <tex>\varepsilon</tex>-приближенной  сложностью <tex>O (mn^3(\log(n) + \log(1 / \varepsilon) + \log(\max\limits_{i=1}^{n} p_i)) </tex>, потому как <tex>L_{max}</tex>, ограничен <tex>n \max\limits_{i=1}^{n}p_i</tex>, при <tex>s_1 = 1</tex>.
  
Задача <tex>Q | pmtn; r_i | C_{max}</tex> представляет собой частный случай <tex>Q | pmtn; r_i | L_{max}</tex>, и может быть решена более эффективно. Labetoulle, Lawler, Lenstra, и Rinnooy Kan разработали алгоритм работающий за <tex> O(n log(n) + mn) </tex> специально для этого случая.
+
Задача <tex>Q \mid pmtn; r_i \mid C_{max}</tex> представляет собой частный случай <tex>Q \mid pmtn; r_i \mid L_{max}</tex>, и может быть решена более эффективно<ref>Описано в Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 133 стр.</ref>.
{{Утверждение
 
|statement= Задача <tex>Q | pmtn | L_{max}</tex> может быть решена за <tex> O(n log(n) + mn) </tex> шагов.
 
|proof=
 
Решение <tex>Q | pmtn; r_i | C_{max}</tex> эквивалентно нахождению наименьшего  <tex>T \ge 0</tex>, такого, что задача с допустимым временным интервалом <tex>[r_i, T] (i = 1, . . . , n)</tex> имеет решение.
 
  
С другой стороны, решение <tex>Q | pmtn | L_{max}</tex> эквивалентно нахождению такого наименьшего <tex>T \ge 0</tex>, такого, что задача с временным интервалом <tex>[0, d_i + T]</tex> или <tex>[−T, d_i]</tex> имеет решение.
+
==Примечания==
}}
+
<references/>
Таким образом, задачи <tex>Q | pmtn; r_i | Cmax</tex> и <tex>Q | pmtn | L_{max}</tex> симметричны.
 
  
==Источники==
+
==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8
+
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 129 {{---}} 133 стр. {{---}} ISBN 978-3-540-69515-8
  
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Версия 05:08, 19 мая 2016

[math]Q \mid pmtn, r_i \mid L_{max}[/math]

Задача:
Рассмотрим задачу на нахождение расписания:
  1. У нас есть несколько станков, работающих параллельно. У станков могут быть разные скорости выполнения работ.
  2. Есть несколько заданий, каждое имеет своё время появления [math]r_i[/math] и время окончания [math]d_i[/math].
  3. Работа может быть прервана в любой момент и продолжена позже на любой машине.
Требуется минимизировать максимальное опоздание [math]L_{max} = \max\limits_i \{C_i - d_i\}[/math].


Алгоритм

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

Рис. 1. Исходная сеть
Рис. 2. Расширение сети


Как в задаче [math]P \mid pmtn, r_i \mid L_{max}[/math] применим метод двоичного поиска и сведем задачу к [math] Q \mid pmtn, r_i, d_i \mid - [/math]. Для существования расписания с [math] L_{max} \leqslant L^* [/math] требуется, чтобы у работы с номером [math] i [/math] выполнялось [math] C_i - d_i \leqslant L^* [/math], что эквивалентно [math] C_i \leqslant d_i + L^* [/math]. Опишем алгоритм решения [math] Q \mid pmtn, r_i, d_i \mid - [/math] при помощи сведения к задаче поиска максимального потока.

Пусть [math] t_1 \leqslant t_2 \leqslant ... \leqslant t_r [/math] — упорядоченная последовательность всех значений [math]r_i[/math] и [math]d_i + L^*[/math]. Определим интервалы на исходной сети (Рис. 1) [math] I_K := [t_{K-1}, t_K], \ T_K = t_K-t_{K-−1} [/math] для [math] K = 2,..., r [/math]. Cчитаем, что станки занумерованы в порядке невозрастания скоростей [math] s_1 \geqslant s_2 \geqslant . . . \geqslant s_m [/math] (также считаем [math]s_{m+1} = 0[/math]).

Искомая сеть строится с помощью расширения сети из задачи [math]P \mid pmtn, r_i \mid L_{max}[/math]. Обозначим через [math] J_{i_1}, J_{i_2}, . . . , J_{i_s} [/math] набор предшественников узла [math]I_K[/math], тогда замененная нами подсеть определяется как [math] I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} [/math].

Расширение сети показано на Рис. 2.

Расширенная подсеть строится путем добавления к вершинам [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]\nu = 1,. . . , s[/math] и [math]j = 1,. . ., m[/math] существует дуга из [math]J_{i_\nu}[/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).

Корректность и оптимальность алгоритма

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

[math](b) \Rightarrow (a)[/math]

Рассмотрим в расширенной сети поток величиной [math]\sum\limits_{i = 1}^n {p_i}[/math]. Обозначим через [math]x_{iK}[/math] общий поток, который идет от [math]J_i[/math] до [math]I_K[/math]. Заметим, что [math]\sum\limits_{i = 1}^n \sum\limits_{K = 2}^r x_{iK} = \sum\limits_{i = 1}^n p_i[/math]. Достаточно показать, что для каждого подмножества [math]A \subseteq \{ 1, . . . , n \}[/math] выполняется
[math]\sum\limits_{i \in A} x_{iK} \leqslant T_Kh(A)[/math] ,где [math]h(A) = \begin{cases} S_{|A|}, & \text{if }|A| \leqslant m \\ S_m, & \text{otherwise} \end{cases} [/math].
Это означает, что условие [math]\sum\limits_{i \in A} p_i \leqslant Th(A), \forall A \subseteq \{ 1, ... , n \}[/math] выполняется и требования к обработке [math]x_{1K}, . . . , x_{nK}[/math] могут быть запланированы как [math]I_K[/math] для [math]K = 2, . . . , r[/math]. Рассмотрим подсеть в расширенной сети в подмножестве [math]A[/math] и соответствующие части потока. Фрагмент частичного потока, который проходит через [math](K, j)[/math] ограничен
[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].
Таким образом, мы имеем

[math]\sum\limits_{i \in A} x_{iK} \geqslant T_K \sum\limits_{j = 1}^m(s_j −- s_{j+1}) \min \{ j, |A| \} = T_Kh(A)[/math]. [math](*)[/math]

То, что равенство [math](*)[/math] справедливо, может рассматриваться как следствие. Если [math]|A| \gt m[/math], то
[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].
В противном случае
[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]

Предположим, что допустимое расписание существует. Для [math]i = 1, ... , n [/math] и [math]K = 2, ..., r[/math] пусть [math]x_{iK}[/math] является "объемом работ", который будет выполняться в интервале [math]I_K[/math] в соответствии с нашим возможным расписанием. Тогда для всех [math]K = 2, ..., r[/math] и произвольных наборов [math]A \subseteq \{ 1, . . . , n \}[/math], неравенство

[math]\sum\limits_{i \in A} x_{iK} \leqslant T_Kh(A)[/math] [math](**)[/math]

выполняется. Кроме того, для [math]i = 1, . . . , n[/math] у нас [math]p_i = \sum\limits_{K = 2}^r s_{iK}[/math]. Остается показать, что можно отправить [math]x_{iK}[/math] от [math]J_i[/math] до [math]I_K[/math] [math](i = 1, . . . , n; K = 2, . . . , r)[/math] в расширенной сети. Такой поток существует, если [math]\forall A \subseteq \{ 1, . . . , n \}[/math] и [math]K = 2, . . . , r[/math] значение [math]\sum\limits_{i \in A} x_{iK}[/math] ограничено величиной минимального разреза части сети с истоками [math]J_i(i \in A)[/math] и стоком [math]I_K[/math]. Тем не менее, это значение

[math]T_K\sum\limits_{j = 1}^m \min \{ j, |A| \}(s_j - s_{j+1})[/math]

Используя [math](**)[/math] и правую часть [math](*)[/math], получаем

[math]\sum\limits_{i \in A} x_{iK} \leqslant T_K h(A) = T_K \sum\limits_{j = 1}^m \min \{ j, |A| \}(s_j - s_{j+1})[/math]

что и является искомым неравенством.
[math]\triangleleft[/math]

Время работы

Работа с максимальным потоком в расширенной сети занимает [math]O (m n^3)[/math] шагов, проверка может быть сделана с такой же скоростью. Для решения [math]Q \mid pmtn; r_{i} \mid L_{max}[/math] мы используем бинарный поиск, а значит, получаем алгоритм с [math]\varepsilon[/math]-приближенной сложностью [math]O (mn^3(\log(n) + \log(1 / \varepsilon) + \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 \mid pmtn; r_i \mid C_{max}[/math] представляет собой частный случай [math]Q \mid pmtn; r_i \mid L_{max}[/math], и может быть решена более эффективно[1].

Примечания

  1. Описано в Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 133 стр.

Источники информации

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