251
правка
Изменения
→Корректность и оптимальность алгоритма
<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>. Рассмотрим еще одну задачу на нахождение расписания:}}
===Корректность и оптимальность алгоритма===
{{Теорема
|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 \in A} p_i \le 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>.
:Таким образом, мы имеем
<table align = center><tr><td><tex>\sum\limits_{i \in A} x_{iK} \ge geqslant T_K \sum\limits_{j = 1}^m(s_j − - s_{j+1}) \min \{ j, |A| \} = T_Kh(A)</tex>. <tex>(5.9*)</tex></td></tr></table>
:То, что равенство <tex>(5.9*) </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>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>(|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>:Предположим, что допустимое расписание существует. Для <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} \le leqslant T_Kh(A)</tex> <tex> (5.10**)</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| \}(s_j - s_{j+1})</tex>
Используя <tex>(5.10**) </tex> и правую часть <tex>(5.9*)</tex>, получаем
<tex>\sum\limits_{i \in A} x_{iK} \le 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; r_i | \mid C_{max}</tex> представляет собой частный случай <tex>Q | \mid pmtn; r_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 | L_{max---}}</tex> может быть решена за <tex> O(n log(n) + mn) </tex> шагов«Springer», 2006 г.|proof= Решение <tex>Q | pmtn; r_i | C_{max{---}}</tex> эквивалентно нахождению наименьшего <tex>T \ge 0</tex>, такого, что задача с допустимым временным интервалом <tex>[r_i, T] (i = 1, 133 стр. . . , n)</texref> имеет решение.
==Источникиинформации==* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 129 {{---}} 133 стр. {{---}} ISBN 978-3-540-69515-8
[[Категория: Теория расписаний]]