Изменения
Нет описания правки
==Постановка задачи==
[[Файл:Figure_5.2.png|400px|thumb|right|Рис. 1]]Рассмотрим еще одну задачу нахождения на нахождение расписания со следующим свойством:
==Алгоритм решения==
[[Файл:Figure_5.29.a.png|400px200px|thumb|right|Рис. 2. 1]]
Применим бинарный поиск для общего решения задачи. Сведем Таким образом сведем задачу к поиску потока сети.
Пусть <tex> t_1 < t_2 <...< t_r </tex> упорядоченная последовательности всех значений <tex>r_i</tex> и <tex>d_i</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</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.1; Расширение сети показано на рисунке Рис 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>ν = 1,. . . , s</tex> и <tex>j = 1,. . ., m</tex> существует дуга из <tex>J_{i_ν}</tex> в <tex>(K, J)</tex> с емкостью <tex> (s_j - s_{j+1}) T_K </tex>.
}}
==Время работы==
[[Файл:Figure_5.9.ab.png|200px500px|thumb|right|Рис. 2.12 - Расширение сети]]
Из-за максимального потока в расширенной сети могут быть рассчитаны в <tex>O (m n^3)</tex> шагов, возможность проверки может быть сделано с такой же сложности. Для решения задачи <tex>Q|pmtn; r_{i}|L_{max}</tex> мы используем бинарный поиск. Получается алгоритм со сложностью <tex>O (mn^3(log(n) + 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 | 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</tex> симметричны.
==Источники==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8
[[Категория: Теория расписаний]]
