Изменения
→Решение
|definition = <ol>
<li>Имеется <tex>M</tex> однородных машин, работающих параллельно.</li>
<li>Есть <tex>Nn</tex> работ, каждое имеет своё время появления <tex>r_i</tex> и время окончания <tex>d_i</tex>.</li>
<li>Работа может быть прервана и продолжена позже.</li>
</ol>
Необходимо составить такое расписание, чтобы значение <tex>L_{max} = \max\limits_{i=1..\ldots n} (C_i - d_i)</tex> было минимальным.}}
== Решение ==
[[Файл:Figure_5.2.png|400px|thumb|right|Рис. 1 - . Cеть]]
Сведем эту задачу к поиску максимального потока в сети, построенной указанным ниже образом.
Работам <tex>J_i</tex> сопоставим свой тип вершин, а интервалам <tex>I_K</tex> свой. Добавим две фиктивные вершины <tex>s</tex> и <tex>t</tex>. Вершина <tex>s</tex> соединена с вершинами <tex>J_i</tex> ребрами с пропускной способностью <tex>p_i</tex>, вершина <tex>t</tex> соединена с вершинами <tex>I_K</tex> ребрами с пропускной способностью <tex>mT_K</tex>. Ребро между вершиной <tex>J_i</tex> и вершиной <tex>I_K</tex> существует, если <tex>r_i \leqslant t_K, t_{K+1} \leqslant d_i</tex>. Пропускная способность этого ребра - <tex>T_K</tex>.
Нетрудно понять, что расписание существует, если максимальный поток через эту сеть равен <tex>\sum_sum\limits_{i=1}^n p_i</tex>.
Если это так, то поток <tex>x_{iK}</tex> на дуге <tex>(J_i, I_K)</tex> соответствует тому, что работа <tex>J_i</tex> будет выполняться во временном интервале <tex>I_K</tex>, и будет справедливо следующее:
# <tex>\sum_sum\limits_{K=1}^{r-1} x_{iK} = p_i, i = 1 \ldots n</tex># <tex>\sum_sum\limits_{i=1}^n x_{iK} \leqslant mT_K, K = 1 \ldots r - 1</tex>
# <tex>x_{iK} \leqslant T_K</tex> для всех ребер <tex>(J_i, I_K)</tex>
Исходя из этого, расписание строится выполнением работы <tex>J_{iK}</tex> с временем выполнения <tex>x_{iK} > 0</tex> в интервале <tex>I_K</tex>.
Т.к. сеть содержит <tex>O(Nn)</tex> элементов, значит максимальный поток в ней можно найти за <tex>O(n^3)</tex>. Кроме того, построение "окон" выполнения работ займет <tex>O(Nn^2)</tex>. Т.о. указанный выше алгоритм потребует <tex>O(Nn^3)</tex> операций.
Для решения данной задачи мы используем бинпоиск по <tex>L</tex> значениям, а значит, получаем алгоритм с <tex>\varepsilon</tex>-приближенной сложностью <tex>O (n^3(\log(n) + \log(\cfrac{1 / }{\varepsilon}) + \log(\max\limits_{j=1..\ldots n} (p_j))) </tex>, потому как <tex>L_{max}</tex>, ограничен <tex>n\max\limits_{j=1..\ldots n} (p_j)</tex>
[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]
