33
правки
Изменения
Нет описания правки
Пусть <tex>t_1 < t_2 < \ldots < t_r</tex> - упорядоченная последовательность <tex>r_i</tex> и <tex>d_i</tex>. Определим интервалы <tex>I_K = [t_K; t_{K+1}]</tex> с длиной <tex>T_K = t_{K+1} - t_K</tex> для всех <tex>K = 1 \ldots r-1</tex>.
Работам <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 \le leqslant t_K, t_{K+1} \le leqslant d_i</tex>. Пропускная способность этого ребра - <tex>T_K</tex>.
Нетрудно понять, что расписание существует, если максимальный поток через эту сеть равен <tex>\sum_{i=1}^n p_i</tex>.
# <tex>\sum_{K=1}^{r-1} x_{iK} = p_i, i = 1 \ldots n</tex>
# <tex>\sum_{i=1}^n x_{iK} \le leqslant mT_K, K = 1 \ldots r - 1</tex># <tex>x_{iK} \le leqslant T_K</tex> для всех ребер <tex>(J_i, I_K)</tex>
Исходя из этого, расписание строится выполнением работы <tex>J_{iK}</tex> с временем выполнения <tex>x_{iK} > 0</tex> в интервале <tex>I_K</tex>.
Для решения данной задачи мы используем бинпоиск по <tex>L</tex> значениям, а значит, получаем алгоритм с <tex>\varepsilon</tex>-приближенной сложностью <tex>O (n^3(log(n) + log(1 / \varepsilon) + log(\max\limits_{j=1}^{n} p_j)) </tex>, потому как <tex>L_{max}</tex>, ограничен <tex>n \max\limits_{j=1}^{n}p_j</tex>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
