Изменения

<div styletex dpi ="background-color200">Q \mid pmtn, r_i \mid L_{max}</tex>{{Задача|definition=Рассмотрим задачу на нахождение расписания: #ABCDEF; fontУ нас есть несколько станков, работающих параллельно. У станков могут быть разные скорости выполнения работ.# Есть несколько заданий, каждое имеет своё время появления <tex>r_i</tex> и время окончания <tex>d_i</tex>.# Работа может быть прервана в любой момент и продолжена позже на любой машине.Требуется минимизировать максимальное опоздание <tex>L_{max} = \max\limits_i \{C_i -sized_i\}</tex>. }} ==Алгоритм=====Алгоритм решения===<table><tr><td>[[Файл:Figure_5.2.png|500px|thumb|Рис. 1. Исходная сеть]]</td><td>[[Файл: 16px; fontFigure_5.9.b.png|500px|thumb|Рис. 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> t_1 \leqslant t_2 \leqslant ... \leqslant t_r </tex> {{---weight}} упорядоченная последовательность всех значений <tex>r_i</tex> и <tex>d_i + L^*</tex>.Определим интервалы на исходной сети (Рис. 1) <tex> I_K : bold; color: #000000; text= [t_{K-1}, t_K], \ T_K = t_K-align: center; padding: 4px; bordert_{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>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>. Расширение сети показано на Рис. 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 -style: solid; borders_{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 -width: 1px;"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</divtex> пропускной способностью <tex>S_mT_K</tex> (Рис. 1). ===Корректность и оптимальность алгоритма==={{Теорема|statement=Следующие утверждения эквивалентны::<tex>(a)<includeonly/tex>[[КатегорияСуществует допустимое расписание.: <tex>(b)</tex> В разработке]]расширенной сети существует поток от <tex>s</tex> до <tex>t</tex> со значением <tex>\sum\limits_{i=1}^n p_i</tex>. |proof=<tex>(b) \Rightarrow (a)</includeonlytex>

:Рассмотрим в расширенной сети поток величиной <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>r_i\sum\limits_{i \in A} x_{iK} \leqslant T_Kh(A)</tex> и срок завершения(дедлайн) ,где <tex>d_ih(A) = \begin{cases} S_{|A|}, & \text{if }|A| \leqslant m \\ S_m, & \text{otherwise}\end{cases} </tex>.

==Алгоритм решения==[[Файл:Figure_5Это означает, что условие <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, .png|400px|thumb|right|Рис. 1]]. , 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>.

Также определим <table align = center><tr><td><tex> I_K := [t_\sum\limits_{i \in A} x_{K-1iK}, t_K],\ geqslant T_K \sum\limits_{j = t_K1}^m(s_j −-t_s_{j+1}) \min \{K-−1j, |A| \} = T_Kh(A)</tex> для . <tex> K = 2,..., r (*)</tex>.</td></tr></table>

Далее мы расширяем сеть:То, что равенство <tex>(*)</tex> справедливо, может рассматриваться как следствие. Если <tex>|A| > m</tex>, показанную на рисунке 1 следующим образом:то

:<tex>I_K</tex> - произвольный интервал узел на рисунке, обозначим через <tex> J_\sum\limits_{i_1j = 1}^m \min \{ j, J_|A| \}(s_j - s_{i_2j + 1}, ) = s_1 - s_2 + 2s_2 - 2s_3 + 3s_3 - 3s_4 + . . . , J_+ ms_s - ms_{i_sm+1} =\ </tex> набор предшественников узла <tex>I_K</tex>. Тогда замененная нами подсеть определяется как :<tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} S_m = h(A)</tex>, которая показана на рисунке 2.1; Расширение сети показано на рисунке 2.2.

Расширенная подсеть строится путем добавления к вершинам :<tex> I_K, J_\sum\limits_{i_1j = 1}, J_\min \{i_2}j, . . . , J_{i_s|A| \} </tex> вершин <tex>(K, s_j - s_{j + 1}), (K, 2), = s_1 - s_2 + 2s_2 - 2s_3 + 3s_3 - . . . + (K, m|A| - 1) </tex>. При <tex>j = s_{|A| - 1,..., m } -\ </tex>, есть дуги от :<tex>(K, j|A| - 1)</tex> до <tex>I_K</tex> с емкостью <tex> js_{|A|} + |A|(s_j s_{|A|} - s_{j+|A| - 1}) T_K </tex> и для всех <tex>ν = 1,- . . . , s</tex> и <tex>j = 1,. . ., m</tex> существует дуга из <tex>J_{i_ν}</tex> в <tex>(K, J)</tex> с емкостью <tex> (s_j - s_m + s_m - s_{jm +1}) T_K = S_{|A|} = h(A)</tex>.

Для каждого <tex>I_K(a) \Rightarrow (b)</tex> у нас есть такие расширения<br>:Предположим, что допустимое расписание существует. Кроме того, мы сохраняем дуги из Для <tex>si = 1, ... , n </tex> в и <tex>J_iK = 2, ..., r</tex> емкостью пусть <tex>p_ix_{iK}</tex> и дуги из является "объемом работ", который будет выполняться в интервале <tex>I_K</tex> в соответствии с нашим возможным расписанием. Тогда для всех <tex>tK = 2, ..., r</tex> емкостью и произвольных наборов <tex>S_mT_KA \subseteq \{ 1, . . . , n \}</tex> (см. рисунок 1)., неравенство

:<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>T_K\sum\limits_{j = 1}^m \min \{ j, |A|statement=Следующие свойства эквивалентны:\}(s_j - s_{j+1})</tex> Используя <tex>(**)</tex> и правую часть <tex>(*)</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>

===Время работы=== Работа с максимальным потоком в расширенной сети занимает <tex>Q | pmtn; ri | CmaxO (m n^3)</tex> представляет собой частный случай шагов, проверка может быть сделана с такой же скоростью. Для решения <tex>Q | \mid pmtn; ri | Lmaxr_{i} \mid L_{max}</tex>мы используем бинарный поиск, и может быть решена более эффективно. Labetoulle, Lawler, Lenstraа значит, и Rinnooy Kan разработали получаем алгоритм работающий за с <tex> O(n log(n) + mn) \varepsilon</tex> специально для этого случая.{{Утверждение|statement= Задача <tex>Q | pmtn | Lmax</tex> может быть решена за -приближенной сложностью <tex> O(mn^3(\log(n ) + \log(1 / \varepsilon) + \log(\max\limits_{i=1}^{n} p_i) + mn) </tex> шагов.|proof= Решение , потому как <tex>Q | pmtn; ri | CmaxL_{max}</tex> эквивалентно нахождению наименьшего , ограничен <tex>T n \max\ge 0limits_{i=1}^{n}p_i</tex>, такого, что задача с "временными окнами" при <tex>[r_i, T] (i s_1 = 1, . . . , n)</tex> имеет решение.

С другой стороны, решение Задача <tex>Q | \mid pmtn | Lmax; r_i \mid C_{max}</tex> эквивалентно нахождению такого наименьшего представляет собой частный случай <tex>T Q \ge 0mid pmtn; r_i \mid L_{max}</tex>, такого, что задача с "временными окнами" и может быть решена более эффективно<texref>[0Описано в Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», d_i + T]2006 г. {{---}} 133 стр.</texref> или с "временными окнами" . ==Примечания==<texreferences/>[−T ==Источники информации==* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», d_i]</tex> имеет решение2006 г. {{---}} 129 {{---}} 133 стр.{{---}}ISBN 978-3-540-69515-8 [[ФайлКатегория:Figure_5.9.b.png|500px|thumb|right|Рис. 2.2Теория расписаний]]Таким образом, задачи <tex>Q | pmtn; ri | Cmax</tex> и <tex>Q | pmtn | Lmax</tex> симметричны.