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], которая показана на рисунке 2.1; Расширение сети показано на рисунке 2.2.

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] с емкостью [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] с емкостью [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] (см. рисунок 1).

Теорема:

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

Время работы

Рис. 2.1

Из-за максимального потока в расширенной сети могут быть рассчитаны в [math]O (m n^3)[/math] шагов, возможность проверки может быть сделано с такой же сложности. Для решения задачи [math]Q|pmtn; r_{i}|L_{max}[/math] мы используем бинарный поиск. Получается алгоритм со сложностью [math]O (mn^3(log(n) + 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].

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

Утверждение:

Задача [math]Q | pmtn | Lmax[/math] может быть решена за [math] O(n log(n) + mn) [/math] шагов.

[math]\triangleright[/math]

Решение [math]Q | pmtn; ri | Cmax[/math] эквивалентно нахождению наименьшего [math]T \ge 0[/math], такого, что задача с "временными окнами" [math][r_i, T] (i = 1, . . . , n)[/math] имеет решение. С другой стороны, решение [math]Q | pmtn | Lmax[/math] эквивалентно нахождению такого наименьшего [math]T \ge 0[/math], такого, что задача с "временными окнами" [math][0, d_i + T][/math] или с "временными окнами" [math][−T, d_i][/math] имеет решение.

[math]\triangleleft[/math]

Рис. 2.2

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