Изменения

Перейти к: навигация, поиск

QpmtnriLmax

227 байт добавлено, 00:28, 17 мая 2016
Нет описания правки
# Есть несколько заданий, каждое имеет своё время появления <tex>r_i</tex> и время окончания <tex>d_i</tex>.
# Работа может быть прервана в любой момент и продолжена позже на любой машине.
Требуется минимизировать максимальное опоздание <tex>L_{max} = \max\limits_i \{C_i - d_i\}</tex> .
}}
 
[[Файл:Figure_5.2.png|400px|thumb|right|Рис. 1 - Исходная сеть]]
==Алгоритм==
===Алгоритм решения===
<table><tr><td>[[Файл:Figure_5.2.png|500px|thumb|Рис. 1 - Исходная сеть]]</td><td>[[Файл:Figure_5.9.b.png|500px|thumb|right|Рис. 2 - Расширение сети]]</td></tr></table> 
Как в [[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> при помощи сведения к задаче поиска [[Определение_сети,_потока|максимального потока]].
Расширенная подсеть строится путем добавления к вершинам <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=Следующие утверждения эквивалентны:
* <tex>(a)</tex> Существует допустимое расписание. * <tex>(b)</tex> В расширенной сети существует поток от <tex>s</tex> до <tex>t</tex> со значением <tex>\sum\limits_{i=1}^n p_i</tex>.
|proof=<tex>(b) \Rightarrow (a):</tex>
Таким образом, мы имеем
<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>
То, что равенство <tex>(*)</tex> справедливо, может рассматриваться как следствие. Если <tex>|A| > m</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>, неравенство
<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>. Тем не менее, это значение
251
правка

Навигация