QpmtnriLmax

Эта статья находится в разработке!

Постановка задачи

Рассмотрим задачу нахождения расписания со следующим свойством:

- Каждое задание имеет своё времени выпуска [math]r_i[/math] и срок завершения(дедлайн) [math]d_i[/math].

Применим бинарный поиск для общего решения задачи. Сведем задачу к поиску потока сети.

Пусть [math] t_1 \lt t_2 \lt ...\lt t_r [/math] упорядоченная последовательности всех значений [math]r_i[/math] и [math]d_i[/math].

Также определим [math] I_K := [t_{K-1}, t_K],\ T_K = t_K-t_{K-−1} [/math] для [math] K = 2,..., r [/math].

Далее мы расширяем сеть, показанную на рисунке 5.2 TODO: ДОБАВИТЬ_Рисунки {5.2} 5.9: Расширение сети. следующим образом:

[math]I_K[/math] - произвольный интервал узел на рисунке, обозначим через [math] J_{i_1}, J_{i_2}, . . . , J_{i_s} [/math] набор предшественников узла [math]I_K[/math].

Тогда замененная нами подсеть определяется как [math] I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} [/math], которая показана на рисунке 5.9 (а), расширение сети показано на рисунке 5.9 (б).

Cчитаем, что машины индексируются в порядке невозрастания скоростей [math] s_1 \ge s_2 \ge . . . \ge s_m [/math], кроме того [math]s_{m+1} = 0[/math].

Расширенная подсеть строится путем добавления к вершинам [math] I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} [/math] вершин [math](K, 1), (K, 2), . . . (K, m) [/math].

При j = 1,..., m, есть дуги от (K, j) до I_K with capacity [math] j(s_j - s_{j+1}) \dot T_K [/math] и для всех ν = 1,. . . , s и j = 1,. . ., m существует дуга из J_{i_ν} в (K, J) with capacity [math] (s_j - s_{j+1}) \dot T_K [/math].

Для каждого [math]I_K[/math] у нас есть такие расширения. Кроме того, мы сохраняем дуги от [math]s[/math] до [math]J_i[/math] и мощностью [math]p_i[/math] дуг из [math]I_K[/math] в [math]t[/math] мощностью [math]S_mT_K[/math] (см. рисунок 5.2). Сеть построена таким образом, называется расширенной сетью.

//=================================================================================================================== Следующая теорема показывает, что мы можем проверить возможность по решению задача о максимальном потоке в расширенной сети. Теоремы 5.9 эквивалентны следующие свойства: (А) Там существует допустимое расписание. (Б) В расширенной сети существует поток с с к т со значением [math]sum_i=1^n{p_i}[/math]

Из-за максимального потока в расширенной сети могут быть рассчитаны в O (mn3) шагов, возможность проверки может быть сделано с такой же сложности. Для решения задачи Q | pmtn; п | Lmax мы бинарный поиск. Это дает ε-приближении алгоритм со сложностью O (mn3 (§ п + журнал (1 / ε) + log ( п. Макс = 1 р)), потому что Lmax, конечно, ограниченной п п. Макс = 1 пи, если s1 = 1. Потому что (5.10) справедливо для всех К частичной работы с требования к обработке Xik могут быть запланированы в ИК с уровнем алгоритма. Проблема Q | pmtn; п | Cmax, которая представляет собой частный случай Q | pmtn; п | Lmax, могут быть решены более эффективно. Labetoulle, Lawler, Ленстра и Rinnooy Кан [133] разработали О (п § п + тп)-алгоритм для этого специальные случае. Кроме того, проблема Q | pmtn | Lmax может быть решена в О (п § п + тп) шагов. Это вытекает из следующих соображений. Проблема Q | pmtn; п | Cmax эквивалентно нахождению наименьшего T ≥ 0, , что проблема с временными окнами [г, т] (г = 1, ..., п) имеет возможности решение. С другой стороны, проблема Q | pmtn | Lmax эквивалентна нахождения наименьшего T ≥ 0 такое, что проблема с временными окнами [0, D + T] или с временными окнами [-T, ди] имеет допустимое решение. Таким образом, проблемы Q | pmtn; п | Cmax и Q | pmtn | Lmax симметричны