QpmtnriLmax

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

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

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

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

Алгоритм решения

Рис. 1

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

Пусть [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].

Далее мы расширяем сеть, показанную на рисунке 1 следующим образом:

[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 (б). TODO: ДОБАВИТЬ_Рисунок 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].

При [math]j = 1,..., m [/math], есть дуги от [math](K, j)[/math] до [math]I_K[/math] with capacity [math] j(s_j - s_{j+1}) T_K [/math] и для всех [math]ν = 1,. . . , s[/math] и [math]j = 1,. . ., m[/math] существует дуга из [math]J_{i_ν}[/math] в [math](K, J)[/math] with capacity [math] (s_j - s_{j+1}) 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). Сеть построена таким образом, называется расширенной сетью.

Теорема:

Следующие свойства эквивалентны: (А) Существует допустимое расписание. (Б) В расширенной сети существует поток от s до t со значением [math]\sum\limits_{i=1}^{n} p_i[/math]

Время работы

Рис. 2.1

Рис. 2.2

Из-за максимального потока в расширенной сети могут быть рассчитаны в [math]O (m n^3)[/math] шагов, возможность проверки может быть сделано с такой же сложности.

Для решения задачи [math]Q|pmtn; r_{i}|L_{max}[/math] мы используем бинарный поиск. Это дает [math]\varepsilon[/math]-приближении алгоритм со сложностью [math]O (mn^3(log(n) + log(1 / \varepsilon) + log (\max\limits_{i=1}^{n} p_i)) [/math], потому что [math]L_{max}[/math], ограничен [math]n \max\limits_{i=1}^{n}p_i[/math], при [math]s_1 = 1[/math].

Потому что (5.10) справедливо для всех К частичной работы с требования к обработке Xik могут быть запланированы в ИК с уровнем алгоритма.

Задача [math]Q | pmtn; ri | Cmax[/math], которая представляет собой частный случай [math]Q | pmtn; ri | Lmax[/math], может быть решена более эффективно. Labetoulle, Lawler, Lenstra, and Rinnooy Kan разработали алгоритм работающий за [math] O(n log(n) + mn) [/math] специально для этого случая.

Задача [math]Q | pmtn | Lmax[/math] может быть решена за [math] O(n log(n) + mn) [/math] шагов. Это вытекает из следующих соображений:

Решение [math]Q | pmtn; ri | Cmax[/math] эквивалентно нахождению наименьшего [math]T \ge 0[/math], что проблема с временными окнами [г, т] (г = 1, ..., п) имеет возможности решение.

С другой стороны, решение [math]Q | pmtn | Lmax[/math] эквивалентно нахождению такого наименьшего [math]T \ge 0[/math], что проблема с временными окнами [0, D + T] или с временными окнами [-T, ди] имеет допустимое решение.

Таким образом, задачи [math]Q | pmtn; ri | Cmax[/math] и [math]Q | pmtn | Lmax[/math] симметричны.