Изменения
Нет описания правки
- Каждое задание имеет своё времени выпуска <tex>r_i</tex> и срок завершения(дедлайн) <tex>d_i</tex>.
==Алгоритм решения==
[[Файл:Figure_5.2.png|400px|thumb|right|Рисунок 1]]
Применим бинарный поиск для общего решения задачи. Сведем задачу к поиску потока сети.
Также определим <tex> I_K := [t_{K-1}, t_K],\ T_K = t_K-t_{K-−1} </tex> для <tex> K = 2,..., r </tex>.
Далее мы расширяем сеть, показанную на рисунке 5.2 1 {{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>.
//===================================================================================================================
Потому что (5.10) справедливо для всех К частичной работы с требования к обработке Xik могут быть запланированы в ИК с уровнем алгоритма. Проблема Задача <tex>Q | pmtn; п ri | Cmax</tex>, которая представляет собой частный случай <tex>Q | pmtn; п ri | Lmax</tex>, могут может быть решены решена более эффективно. Labetoulle, Lawler, Ленстра и Lenstra, and Rinnooy Кан [133] Kan разработали О алгоритм работающий за <tex> O(n log(п § п n) + тпmn)-алгоритм </tex> специально для этого специальные случаеслучая. Кроме того, проблема Задача <tex>Q | pmtn | Lmax </tex> может быть решена в О за <tex> O(n log(п § п n) + тпmn) </tex> шагов. Это вытекает из следующих соображений. Проблема : Решение <tex>Q | pmtn; п ri | Cmax </tex> эквивалентно нахождению наименьшего <tex>T ≥ \ge 0, </tex>, что проблема с временными окнами [г, т] (г = 1, ..., п) имеет возможности решение. С другой стороны, проблема решение <tex>Q | pmtn | Lmax эквивалентна нахождения </tex> эквивалентно нахождению такого наименьшего <tex>T ≥ \ge 0 такое</tex>, что проблема с временными окнами [0, D + T] или с временными окнами [-T, ди] имеет допустимое решение. Таким образом, проблемы задачи <tex>Q | pmtn; ri | Cmax</tex> и <tex>Q | pmtn | Lmax</tex> симметричны.
