Изменения

<includeonlytex dpi = "200">[[Категория: В разработке]]Q \mid pmtn, r_i \mid L_{max}</includeonlytex>{{Задача[[Файл|definition=Рассмотрим задачу на нахождение расписания:Figure_5# У нас есть несколько станков, работающих параллельно.2У станков могут быть разные скорости выполнения работ.png|400px|thumb|right|Рис# Есть несколько заданий, каждое имеет своё время появления <tex>r_i</tex> и время окончания <tex>d_i</tex>. 1 - Исходная сеть]]# Работа может быть прервана в любой момент и продолжена позже на любой машине.Требуется минимизировать максимальное опоздание <tex>L_{max} ==Постановка задачи==\max\limits_i \{C_i - d_i\}</tex>. Рассмотрим еще одну задачу на нахождение расписания:}}

# Каждое задание имеет своё времени выпуска ==Алгоритм=====Алгоритм решения===<textable>r_i<tr><td>[[Файл:Figure_5.2.png|500px|thumb|Рис. 1. Исходная сеть]]</textd><td>[[Файл:Figure_5.9.b.png|500px|thumb|Рис. 2.Расширение сети]]</td># Срок завершения(дедлайн) <tex/tr>d_i</textable>.

==Алгоритм решения==Как в [[Файл:Figure_5.9.a.pngPpmtnriLmax|200pxзадаче]] <tex>P \mid pmtn, r_i \mid L_{max}</tex> применим метод [[Вещественный_двоичный_поиск|thumb|right|Рисдвоичного поиска]] и сведем задачу к <tex> Q \mid pmtn, r_i, d_i \mid - </tex>. 2Для существования расписания с <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>.1 Опишем алгоритм решения <tex> Q \mid pmtn, r_i, d_i \mid - Заменённая подсеть</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 P \mid pmtn, r_i \mid L_{max}</tex> упорядоченная последовательности всех значений . Обозначим через <tex>r_iJ_{i_1}, J_{i_2}, . . . , J_{i_s} </tex> и набор предшественников узла <tex>d_iI_K</tex>.Определим , тогда замененная нами подсеть определяется как <tex> I_K := [t_, J_{K-1i_1}, t_K], \ T_K = t_K-t_J_{K-−1i_2} </tex> для <tex> K = 2,..., r J_{i_s} </tex>.

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

<tex>I_K</tex> - произвольный интервал-узел. Обозначим через <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. 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_ν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>

(Б) В :Рассмотрим в расширенной сети существует поток величиной <tex>\sum\limits_{i = 1}^n {p_i}</tex>. Обозначим через <tex>x_{iK}</tex> общий поток, который идет от s <tex>J_i</tex> до t со значением <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=(b) -> (a):Consider a flow with value <tex>sum_\sum\limits_{i = 1\in A}^n x_{p_iiK}\leqslant T_Kh(A)</tex> in the expanded network. Denote by x_{iK} the total flow which goes from J_i to I_K. Then ,где <tex>sum_{i h(A) = 1}^n sum_\begin{K = 2cases}^r X_ S_{iK|A|} = sum_, & \text{i = 1if }^n p_i</tex>. It is sufficient to show that for each subset <tex>|A ⊆ {1| \leqslant m \\ S_m, . . . , n}</tex> we have <tex>sum_& \text{i∈Aotherwise} x_\end{iKcases} \le T_Kh(A)</tex>.

This means that condition :Это означает, что условие <tex>\sum\limits_{i \in A} p_i \leqslant Th(5A), \forall A \subseteq \{ 1, ...8) holds and the processing requirements , n \}</tex> выполняется и требования к обработке <tex>x_{1K}, . . . , x_{nK}</tex> can be scheduled in могут быть запланированы как <tex>I_K</tex> for для <tex>K = 2, . . . , r</tex>. Consider in the expanded network the subnetwork induced by Рассмотрим подсеть в расширенной сети в подмножестве <tex>A and thecorresponding partial flow</tex> и соответствующие части потока. The portion of this partial flow which goes through Фрагмент частичного потока, который проходит через <tex>(K, j)</tex> is bounded byограничен

:<tex>\min\{j(s_j − - s_{j + 1})T_K, |A|(s_j − - s_{j+1})TK_T_K \} = T_K(s_j − - s_{j+1}) \dot min\{j, |A|\}</tex>.

Thus:Таким образом, we haveмы имеем

<table align = center><tr><td><tex>sum_\sum\limits_{i∈Ai \in A} x_{iK} \ge geqslant T_K sum_\sum\limits_{j = 1}^m(s_j − - s_{j+1}) \min\{j, |A|\} = T_Kh(A)</tex>. <tex>(5.9*)�</tex></td></tr></table>

That the equality in :То, что равенство <tex>(5.9*) holds can be seen as follows</tex> справедливо, может рассматриваться как следствие. If Если <tex>|A| \go > m</tex>, we haveто

:<tex>sum_\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>sum_\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) -> \Rightarrow (b)</tex><br>: Assume that a feasible schedule existsПредположим, что допустимое расписание существует. For Для <tex>i = 1, ... , n </tex> and и <tex>K = 2, ..., r</tex> let пусть <tex>x_{iK}</tex> be the “amount of work” to be performed on job <tex>i</tex> in the interval является "объемом работ", который будет выполняться в интервале <tex>I_K</tex> according to this feasible scheduleв соответствии с нашим возможным расписанием. Then for all Тогда для всех <tex>K = 2, ..., r</tex> and arbitrary sets и произвольных наборов <tex>A ⊆ \subseteq \{1, . . . , n\}</tex>, the inequalityнеравенство

:<table align = center><tr><td><tex>sum_\sum\limits_{i∈Ai \in A} x_{iK} \le leqslant T_Kh(A)</tex> <tex> (5.10**)</tex></td></tr></table>

holdsвыполняется. FurthermoreКроме того, for для <tex>i = 1, . . . , n</tex> we have у нас <tex>p_i = sum_\sum\limits_{K = 2}^r s_{iK}</tex>. It remainsto show that it is possible to send Остается показать, что можно отправить <tex>x_{iK}</tex> units of flow from от <tex>J_i</tex> to до <tex>I_K</tex> <tex>(i = 1, . . . , n; K = 2, . . . , r)</tex> in the expanded networkв расширенной сети. A sufficient condition for the existence of such a flow is that for arbitrary Такой поток существует, если <tex>\forall A ⊆ \subseteq \{1, . . . , n\}</tex> and и <tex>K = 2, . . . , r</tex> the value значение <tex>sum_\sum\limits_{i∈Ai \in A} x_{iK}</tex> is bounded by the value of a minimum cut in the partial network with sources ограничено величиной минимального разреза части сети с истоками <tex>J_i(i ∈ \in A)</tex> and sink и стоком <tex>I_K</tex>. HoweverТем не менее, this value isэто значение

<tex>T_K sum_\sum\limits_{j = 1}^m \min \{j, |A|\}(s_j - s_{j+1})</tex>

Using Используя <tex>(5.10**) and the right-hand side of </tex> и правую часть <tex>(5.9*)</tex>, we getполучаем

<tex>sum_\sum\limits_{i∈Ai \in A} x_{iK} \le T_Khleqslant T_K h(A) = T_K sum_\sum\limits_{j = 1}^m \min\{j, |A|\}(s_j - s_{j+1})</tex>

which is the desired inequalityчто и является искомым неравенством.

===Время работы===

Работа с максимальным потоком в расширенной сети занимает <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 | \mid pmtn; ri | Cmaxr_i \mid C_{max}</tex> представляет собой частный случай <tex>Q | \mid pmtn; ri | Lmaxr_i \mid L_{max}</tex>, и может быть решена более эффективно. Labetoulle, Lawler, Lenstra, и Rinnooy Kan разработали алгоритм работающий за <texref> O(n log(n) + mn) </tex> специально для этого случаяОписано в Peter Brucker.«Scheduling Algorithms» {{Утверждение|statement= Задача <tex>Q | pmtn | Lmax</tex> может быть решена за <tex> O(n log(n) + mn) </tex> шагов.|proof= Решение <tex>Q | pmtn; ri | Cmax</tex> эквивалентно нахождению наименьшего <tex>T \ge 0</tex>, такого, что задача с допустимым временным интервалом <tex>[r_i, T] (i = 1---}} «Springer», 2006 г. {{---}} 133 стр. . , n)</texref> имеет решение.

С другой стороны, решение <tex>Q | pmtn | Lmax</tex> эквивалентно нахождению такого наименьшего <tex>T \ge 0</tex>, такого, что задача с временным интервалом <tex>[0, d_i + T]</tex> или <tex>[−T, d_i]</tex> имеет решение.}}==Примечания==Таким образом, задачи <tex>Q | pmtn; ri | Cmax</tex> и <tex>Q | pmtn | Lmax<references/tex> симметричны.

==Источникиинформации==* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 129 {{---}} 133 стр. {{---}} ISBN 978-3-540-69515-8