Изменения

<div styletex dpi ="background-color200">Q \mid pmtn, r_i \mid L_{max}</tex>{{Задача|definition=Рассмотрим задачу на нахождение расписания: #ABCDEF; font-size: 16px; font-weight: bold; color: У нас есть несколько станков, работающих параллельно. У станков могут быть разные скорости выполнения работ.#000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;"Есть несколько заданий, каждое имеет своё время появления <tex>r_i</tex> и время окончания <tex>Эта статья находится в разработке!d_i</divtex>.# Работа может быть прервана в любой момент и продолжена позже на любой машине.Требуется минимизировать максимальное опоздание <includeonlytex>[[Категория: В разработке]]L_{max} = \max\limits_i \{C_i - d_i\}</includeonlytex>. }}

==Постановка задачиАлгоритм==Рассмотрим задачу нахождения расписания со следующим свойством===Алгоритм решения===<table><tr><td>[[Файл:Figure_5.2.png|500px|thumb|Рис. 1. Исходная сеть]]</td><td>[[Файл:Figure_5.9.b.png|500px|thumb|Рис. 2. Расширение сети]]</td></tr></table>

==Алгоритм решения==Как в [[PpmtnriLmax|задаче]] <tex>P \mid pmtn, r_i \mid L_{max}</tex> применим метод [[Файл:Figure_5Вещественный_двоичный_поиск|двоичного поиска]] и сведем задачу к <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>.png|400px|thumb|rightОпишем алгоритм решения <tex> Q \mid pmtn, r_i, d_i \mid - </tex> при помощи сведения к задаче поиска [[Определение_сети,_потока|Рисунок 1максимального потока]].

Применим бинарный поиск Пусть <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 P \mid pmtn, r_i \mid L_{max}< t_2 /tex>. Обозначим через <tex> J_{i_1}, J_{i_2}, ...< t_r , J_{i_s} </tex> упорядоченная последовательности всех значений набор предшественников узла <tex>r_iI_K</tex> и , тогда замененная нами подсеть определяется как <tex>d_iI_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex>.

Также определим <tex> I_K := [t_{K-1}, t_K],\ T_K = t_K-t_{K-−1} </tex> для <tex> K = Расширение сети показано на Рис. 2,..., r </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_{{TODO | t j+1}) T_K </tex> и для всех <tex>\nu = 1,. . . , s</tex> и <tex>j = ДОБАВИТЬ_Рисунок 51,.9: Расширение сети.., 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>I_Ks</tex> - произвольный интервал узел на рисунке, обозначим через до <tex> J_{i_1}, J_{i_2}, . . . , J_{i_s} t</tex> набор предшественников узла со значением <tex>I_K\sum\limits_{i=1}^n p_i</tex>.

Тогда замененная нами подсеть определяется как |proof=<tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} (b) \Rightarrow (a)</tex>, которая показана на рисунке 5.9 (а), расширение сети показано на рисунке 5.9 (б).

Cчитаем, что машины индексируются :Рассмотрим в порядке невозрастания скоростей расширенной сети поток величиной <tex> s_1 \ge s_2 sum\ge . 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\ge s_m limits_{i = 1}^n p_i</tex>. Достаточно показать, кроме того что для каждого подмножества <tex>s_A \subseteq \{m+1, . . . , n \} = 0</tex>.выполняется

Расширенная подсеть строится путем добавления к вершинам :<tex> I_K, J_\sum\limits_{i_1i \in A}, J_x_{i_2}, . . . , J_{i_siK} \leqslant T_Kh(A)</tex> вершин ,где <tex>h(K, 1A)= \begin{cases} S_{|A|}, (K& \text{if }|A| \leqslant m \\ S_m, 2), . . . (K, m) & \text{otherwise}\end{cases} </tex>.

При :Это означает, что условие <tex>j = \sum\limits_{i \in A} p_i \leqslant Th(A), \forall A \subseteq \{ 1,..., m n \}</tex>, есть дуги от выполняется и требования к обработке <tex>(Kx_{1K}, . . . , j)x_{nK}</tex> до могут быть запланированы как <tex>I_K</tex> with capacity <tex> j(s_j - s_{j+1}) T_K </tex> и для всех <tex>ν K = 12,. . . , sr</tex> и <tex>j = 1,. . ., m</tex> существует дуга из Рассмотрим подсеть в расширенной сети в подмножестве <tex>J_{i_ν}A</tex> в и соответствующие части потока. Фрагмент частичного потока, который проходит через <tex>(K, J)</tex> with capacity <tex> (s_j - s_{j+1}) T_K </tex>.ограничен

Для каждого :<tex>I_K</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, мы сохраняем дуги от <tex>s</tex> до <tex>J_i</tex> и мощностью <tex>p_i</tex> дуг из <tex>I_K</tex> в <tex>t|A| \}</tex> мощностью <tex>S_mT_K</tex> (см. рисунок 5.2). Сеть построена таким образом, называется расширенной сетью.

{{TODO| t = Теоремы 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>

:То, что равенство <tex>(Б*) В расширенной сети существует поток от s до t со значением </tex> справедливо, может рассматриваться как следствие. Если <tex>\sum\limits_{i=1}^{n} p_i|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>O S_m = h(m n^3A)</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) \Rightarrow (b)</tex><br>:Предположим, что (5допустимое расписание существует. Для <tex>i = 1, ... , n </tex> и <tex>K = 2, ..., r</tex> пусть <tex>x_{iK}</tex> является "объемом работ", который будет выполняться в интервале <tex>I_K</tex> в соответствии с нашим возможным расписанием.10) справедливо Тогда для всех К частичной работы с требования к обработке Xik могут быть запланированы в ИК с уровнем алгоритма<tex>K = 2, ..., r</tex> и произвольных наборов <tex>A \subseteq \{ 1, . . ., n \}</tex>, неравенство

Задача :<textable align = center><tr>Q | pmtn; ri | Cmax</textd>, которая представляет собой частный случай <tex>Q | pmtn; ri | Lmax\sum\limits_{i \in A} x_{iK} \leqslant T_Kh(A)</tex>, может быть решена более эффективно. Labetoulle, Lawler, Lenstra, and Rinnooy Kan разработали алгоритм работающий за <tex> O(n log(n) + mn**) </tex> специально для этого случая.</td></tr></table>

Задача выполняется. Кроме того, для <tex>i = 1, . . . , n</tex> у нас <tex>Q | pmtn | Lmaxp_i = \sum\limits_{K = 2}^r s_{iK}</tex>. Остается показать, что можно отправить <tex>x_{iK}</tex> от <tex>J_i</tex> до <tex>I_K</tex> может быть решена за <tex> O(i = 1, . . . , n; K = 2, . . . , r)</tex> в расширенной сети. Такой поток существует, если <tex>\forall A \subseteq \{ 1, . . . , n log\}</tex> и <tex>K = 2, . . . , r</tex> значение <tex>\sum\limits_{i \in A} x_{iK}</tex> ограничено величиной минимального разреза части сети с истоками <tex>J_i(n) + mni \in A) </tex> шагови стоком <tex>I_K</tex>. Это вытекает из следующих соображений:Тем не менее, это значение

Решение <tex>Q T_K\sum\limits_{j = 1}^m \min \{ j, | pmtn; ri A| Cmax</tex> эквивалентно нахождению наименьшего <tex>T \ge 0}(s_j - s_{j+1})</tex>, что проблема с временными окнами [г, т] (г = 1, ..., п) имеет возможности решение.

С другой стороны, решение Используя <tex>Q | pmtn | Lmax(**)</tex> эквивалентно нахождению такого наименьшего и правую часть <tex>T \ge 0(*)</tex>, что проблема с временными окнами [0, D + T] или с временными окнами [-T, ди] имеет допустимое решение.получаем

Таким образом<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>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 | Lmax; r_i \mid L_{max}</tex> симметричны, и может быть решена более эффективно<ref>Описано в Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 133 стр.</ref>. ==Примечания==<references/> ==Источники информации==* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 129 {{---}} 133 стр.{{---}} ISBN 978-3-540-69515-8 [[Категория: Теория расписаний]]