Изменения
Новая страница: «<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1p...»
<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>
==Постановка задачи==
Рассмотрим задачу нахождения расписания со следующим свойством:
- Каждое задание имеет своё времени выпуска <tex>r_i</tex> и срок завершения(дедлайн) <tex>d_i</tex>.
Применим бинарный поиск для общего решения задачи. Сведем задачу к поиску потока сети.
Пусть <tex> t_1 < t_2 <...< t_r </tex> упорядоченная последовательности всех значений <tex>r_i</tex> и <tex>d_i</tex>.
Также определим <tex> I_K := [t_{K-1}, t_K],\ T_K = t_K-t_{K-−1} </tex> для <tex> K = 2,..., r </tex>.
Далее мы расширяем сеть, показанную на рисунке 5.2 {{TODO | t = ДОБАВИТЬ_Рисунки {5.2} 5.9: Расширение сети.}} следующим образом:
<tex>I_K</tex> - произвольный интервал узел на рисунке, обозначим через <tex> J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex> набор предшественников узла <tex>I_K</tex>.
Тогда замененная нами подсеть определяется как <tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex>, которая показана на рисунке 5.9 (а), расширение сети показано на рисунке 5.9 (б).
Cчитаем, что машины индексируются в порядке невозрастания скоростей <tex> s_1 \ge s_2 \ge . . . \ge s_m </tex>, кроме того <tex>s_{m+1} = 0</tex>.
Расширенная подсеть строится путем добавления к вершинам <tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex> вершин <tex>(K, 1), (K, 2), . . . (K, m) </tex>.
При j = 1,..., m, есть дуги от (K, j) до I_K with capacity <tex> j(s_j - s_{j+1}) \dot T_K </tex> и для всех ν = 1,. . . , s и j = 1,. . ., m существует дуга из J_{i_ν} в (K, J) with capacity <tex> (s_j - s_{j+1}) \dot T_K </tex>.
Для каждого <tex>I_K</tex> у нас есть такие расширения. Кроме того, мы сохраняем дуги от <tex>s</tex> до <tex>J_i</tex> и мощностью <tex>p_i</tex> дуг из <tex>I_K</tex> в <tex>t</tex> мощностью <tex>S_mT_K</tex> (см. рисунок 5.2). Сеть построена таким образом, называется расширенной сетью.
//===================================================================================================================
Следующая теорема показывает, что мы можем проверить возможность по решению
задача о максимальном потоке в расширенной сети.
Теоремы 5.9 эквивалентны следующие свойства:
(А) Там существует допустимое расписание.
(Б) В расширенной сети существует поток с с к т со значением <tex>sum_i=1^n{p_i}</tex>
Из-за максимального потока в расширенной сети могут быть рассчитаны в
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 симметричны
<includeonly>[[Категория: В разработке]]</includeonly>
==Постановка задачи==
Рассмотрим задачу нахождения расписания со следующим свойством:
- Каждое задание имеет своё времени выпуска <tex>r_i</tex> и срок завершения(дедлайн) <tex>d_i</tex>.
Применим бинарный поиск для общего решения задачи. Сведем задачу к поиску потока сети.
Пусть <tex> t_1 < t_2 <...< t_r </tex> упорядоченная последовательности всех значений <tex>r_i</tex> и <tex>d_i</tex>.
Также определим <tex> I_K := [t_{K-1}, t_K],\ T_K = t_K-t_{K-−1} </tex> для <tex> K = 2,..., r </tex>.
Далее мы расширяем сеть, показанную на рисунке 5.2 {{TODO | t = ДОБАВИТЬ_Рисунки {5.2} 5.9: Расширение сети.}} следующим образом:
<tex>I_K</tex> - произвольный интервал узел на рисунке, обозначим через <tex> J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex> набор предшественников узла <tex>I_K</tex>.
Тогда замененная нами подсеть определяется как <tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex>, которая показана на рисунке 5.9 (а), расширение сети показано на рисунке 5.9 (б).
Cчитаем, что машины индексируются в порядке невозрастания скоростей <tex> s_1 \ge s_2 \ge . . . \ge s_m </tex>, кроме того <tex>s_{m+1} = 0</tex>.
Расширенная подсеть строится путем добавления к вершинам <tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex> вершин <tex>(K, 1), (K, 2), . . . (K, m) </tex>.
При j = 1,..., m, есть дуги от (K, j) до I_K with capacity <tex> j(s_j - s_{j+1}) \dot T_K </tex> и для всех ν = 1,. . . , s и j = 1,. . ., m существует дуга из J_{i_ν} в (K, J) with capacity <tex> (s_j - s_{j+1}) \dot T_K </tex>.
Для каждого <tex>I_K</tex> у нас есть такие расширения. Кроме того, мы сохраняем дуги от <tex>s</tex> до <tex>J_i</tex> и мощностью <tex>p_i</tex> дуг из <tex>I_K</tex> в <tex>t</tex> мощностью <tex>S_mT_K</tex> (см. рисунок 5.2). Сеть построена таким образом, называется расширенной сетью.
//===================================================================================================================
Следующая теорема показывает, что мы можем проверить возможность по решению
задача о максимальном потоке в расширенной сети.
Теоремы 5.9 эквивалентны следующие свойства:
(А) Там существует допустимое расписание.
(Б) В расширенной сети существует поток с с к т со значением <tex>sum_i=1^n{p_i}</tex>
Из-за максимального потока в расширенной сети могут быть рассчитаны в
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 симметричны
