Планирование для минимизации задержки: метод замены - Жадные алгоритмы

А теперь обсудим задачу планирования, связанную с той, с которой началась эта глава. Несмотря на сходства в формулировке задачи и жадном алгоритме, используемом для ее решения, доказательство оптимальности алгоритма потребует более сложного анализа.

Задача

Вернемся к ситуации с одним ресурсом и набором из n заявок на его использование в течение интервала времени. Будем считать, что ресурс доступен, начиная с времени s. Однако в отличие от предыдущей задачи заявки становятся более гибкими — вместо начального и конечного времени заявка содержит предельное времяd_i и непрерывный интервал времени длиной t_i, а начинаться она может в любое время до своего предельного времени. Каждой принятой заявке должен быть выделен интервал времени длиной t_i, и разным заявкам должны назначаться неперекрывающиеся интервалы.

Существуют разные объективные функции, к оптимизации которых можно было бы стремиться в такой ситуации, и некоторые из них по вычислительной сложности существенно превосходят другие. Здесь мы рассмотрим очень естественную цель, которая может оптимизироваться жадным алгоритмом. Допустим, мы намерены удовлетворить каждую заявку, но некоторые заявки могут быть отложены на более позднее время. Таким образом, начиная с общего начального времени s, каждой заявке i выделяется интервал времени t_i; обозначим этот интервал [s(i), f(i)], где f(i) = s(i) + t_i. Однако в отличие от предыдущей задачи этот алгоритм должен определить начальное время (а следовательно, и конечное время) для каждого интервала.

Заявка i будет называться задержанной, если она не успевает завершиться к предельному времени, то есть если f(i) > d_i. Задержка такой заявки i определяется по формуле l_i = f(i) - d_i. Будем считать, что если заявка не является просроченной, то l_i = 0. Целью новой задачи оптимизации будет планирование всех заявок с неперекрывающимися интервалами, обеспечивающее минимизацию максимальной задержки L = max_il_i. Эта задача естественным образом встречается при планировании вычислительных заданий, которые должны выполняться на одном компьютере, поэтому мы будем называть заявки “заданиями”.

На рис. 4.5 изображен пример с тремя заданиями: первое имеет длину t₁ = 1 c предельным временем d₁ = 2, у второго t₂ = 2 и d₂ = 4, и у третьего t₃ = 3 и d₃ = 6. Нетрудно убедиться в том, что при планировании заданий в порядке 1, 2, 3 максимальная задержка равна 0.

Рис. 4.5. Пример планирования с минимизацией задержки

Проектирование алгоритма

Как же должен выглядеть жадный алгоритм для такой задачи? Есть несколько естественных жадных решений, в которых мы просматриваем данные заданий (t_i, d_i) и используем эту информацию для упорядочения заданий по некоторому простому правилу.

♦ Одно из решений заключается в планировании заданий по возрастанию длины t для того, чтобы поскорее избавиться от коротких заданий. Впрочем, примитивность такого решения сразу же становится очевидной, поскольку оно полностью игнорирует предельное время выполнения заданий. В самом деле, рассмотрим пример с двумя заданиями: у первого t₁ = 1 и d₁ = 100, а у второго t₂ = 10 и d₂ = 10. Для достижения задержки L = 0 второе задание должно начаться немедленно (и на самом деле запуск второго задания в первую очередь является оптимальным решением).

♦ Предыдущий пример предполагает, что нам следует ориентироваться на задания с очень малым запасом времениd_i - t_i, то есть задания, которые должны запускаться с минимальной задержкой. Таким образом, более естественный жадный алгоритм должен сортировать задания в порядке возрастания запаса времени d_i - t_i.

К сожалению, это жадное правило тоже не работает. Рассмотрим пример из двух заданий: у первого задания t₁ = 1 и d₁ = 2, а у второго t₂ = 10 и d₂ = 10. Сортировка по возрастанию запаса времени поместит второе задание на первое место в расписании, и первое задание создаст задержку 9. (Оно завершается во время 11, на 9 единиц позже предельного времени.) С другой стороны, если начать с планирования первого задания, то оно завершится вовремя, а второе задание ограничится задержкой 1.

Тем не менее существует столь же простой жадный алгоритм, который всегда приводит к оптимальному решению. Задания просто сортируются в порядке возрастания предельного времени d и планируются в этом порядке. Это правило основано на интуитивно понятном принципе: задания с более ранним предельным временем завершаются в первую очередь. В то же время немного трудно поверить, что этот алгоритм всегда выдает оптимальные решения, — просто потому, что он вообще не рассматривает длину заданий. Ранее мы уже раскритиковали метод сортировки длин на основе того, что он игнорировал половину входных данных (предельное время), а сейчас рассматриваем решение, которое теряет другую половину данных. Тем не менее правило первоочередного выбора самого раннего предельного времени выдает оптимальные решения, и сейчас мы это докажем.

Но сначала введем обозначение, которое пригодится при рассмотрении алгоритма. Переименовывая задания в случае необходимости, можно принять, что задания помечены в порядке следования их предельного времени, то есть выполняется условие

Все задания просто планируются в этом порядке. И снова пусть 5 является начальным временем для всех заданий. Задание 1 начинается во время s = s(1) и заканчивается во время f(1) = s(1) + t₁; задание 2 начинается во время s(2) = f(1) и завершается во время f(2) = s(2) + t₂ и т. д. Время завершения последнего спланированного задания будет обозначаться f. Ниже приведена формулировка алгоритма на псевдокоде.

Анализ алгоритма

Чтобы рассуждать об оптимальности алгоритма, сначала следует заметить, что он не оставляет интервалов, когда машины простаивают, хотя еще остались задания. Время, проходящее в таких интервалах, будет называться временем простоя: работа еще осталась, но по какой-то причине машина ничего не делает. У расписания A, построенного по нашему алгоритму, время простоя отсутствует; но также очень легко понять, что существует оптимальное расписание, обладающее таким свойством. Доказательство этого утверждения не приводится.

(4.7) Существует оптимальное расписание без времени простоя.

Как теперь доказать, что наше расписание A оптимально, то есть его максимальная задержка L настолько мала, насколько это возможно? Как и в предыдущих случаях, начнем с рассмотрения оптимального расписания O. Нашей целью будет постепенная модификация O, которая будет сохранять оптимальность на каждом шаге, но в конечном итоге преобразует его в расписание, идентичное расписанию A, найденному жадным алгоритмом. Такой метод анализа называется заменой, и вскоре вы увидите, что он весьма эффективен для описания жадных алгоритмов.

Для начала попробуем охарактеризовать полученные расписания. Будем говорить, что расписание A' содержит инверсию, если задание i с предельным временем d_i предшествует другому заданию j с более ранним предельным временем d_j < d_i. Обратите внимание: по определению расписание A, построенное нашим алгоритмом, не содержит инверсий. Если существует несколько заданий с одинаковыми значениями предельного времени, то это означает, что может существовать несколько разных расписаний без инверсий. Тем не менее мы можем показать, что все эти расписания обладают одинаковой максимальной задержкой L.

(4.8) Все расписания, не содержащие инверсий и простоев, обладают одинаковой максимальной задержкой.

Доказательство. Если два разных расписания не содержат ни инверсий, ни простоев, то задания в них могут следовать в разном порядке, но при этом различаться будет только порядок заданий с одинаковым предельным временем. Рассмотрим такое предельное время d. В обоих расписаниях задания с предельным временем d планируются последовательно (после всех заданий с более ранним предельным временем и до всех заданий с более поздним предельным временем). Среди всех заданий с предельным временем d последнее обладает наибольшей задержкой, причем эта задержка не зависит от порядка заданий. ■

Главным шагом демонстрации оптимальности алгоритма будет установление наличия оптимального расписания, не содержащего инверсий и простоев. Для этого мы начнем с любого оптимального расписания, не имеющего времени простоя; затем оно будет преобразовано в расписание без инверсий без увеличения максимальной задержки. Следовательно, расписание, полученное после этого преобразования, также будет оптимальным.

(4.9) Существует оптимальное расписание, не имеющее инверсий и времени простоя.

Доказательство. Согласно (4.7), существует оптимизация расписание O без времени простоя. Доказательство будет состоять из серии утверждений, первое из которых доказывается легко.

(а) Если O содержит инверсию, то существует такая пара заданий i и j, для которых j следует в расписании немедленно после i и d_j < d_i.

Рассмотрим инверсию, в которой задание а стоит в расписании где-то до задания b и d_a > d_b. При перемещении в порядке планирования заданий от а к b где-то встретится точка, в которой предельное время уменьшается в первый раз. Она соответствует паре последовательных заданий, образующих инверсию. Теперь допустим, что O содержит как минимум одну инверсию, и в соответствии с (а) пусть i и j образуют пару инвертированных запросов, занимающих последовательные позиции в расписании. Меняя местами заявки i и j в расписании O, мы уменьшим количество инверсий в O на 1. Пара (i, j) создавала инверсию в O, перестановка эту инверсию устраняет, и новые инверсии при этом не создаются. Таким образом,

(b) После перестановки i и j образуется расписание, содержащее на 1 инверсию меньше.

В этом доказательстве труднее всего обосновать тот факт, что расписание после устранения инверсии также является оптимальным.

(c) Максимальная задержка в новом расписании, полученном в результате перестановки, не превышает максимальной задержки O.

Очевидно, что если удастся доказать (с), то задачу можно считать выполненной. Исходное расписание О может иметь не более инверсий (если инвертированы все пары), а следовательно, после максимум перестановок мы получим оптимальное расписание без инверсий. ■

Итак, докажем (c) и продемонстрируем, что перестановка пары последовательных инвертированных заданий не приведет к возрастанию максимальной задержки L расписания.

Доказательство (c). Введем вспомогательное обозначение для описания расписания O: предположим, каждая заявка r планируется на интервал времени [s(r), f(r)] и обладает задержкой l'_r. Пусть L' = max_rl'_r обозначает максимальную задержку этого расписания. Обозначим расписание с перестановкой обозначения будут представлять соответствующие характеристики расписания с перестановкой.

Рис. 4.6. Эффект перестановки двух последовательных заданий с инверсией

Теперь вернемся к двум смежным инвертированным заданиям i и j. Ситуация выглядит примерно так, как показано на рис. 4.6: время завершения j до перестановки в точности равно времени завершения i после перестановки. Таким образом, все задания, кроме i и j, в двух расписаниях завершаются одновременно. Кроме того, задание j в новом расписании завершится раньше, а следовательно, перестановка не увеличивает задержку задания j.

Следовательно, остается беспокоиться только о задании i: его задержка могла увеличиться. Что, если это привело к возрастанию максимальной задержки всего расписания? После перестановки задание i завершается во время f(j), в которое завершалось задание j в расписании О. Если задание У “опаздывает” в новом расписании, его задержка составляет Но здесь принципиально то, что i не может задерживаться в расписании больше, чем задерживалось задание j в расписании O. А конкретнее, из нашего предположения d_i > d_j следует, что

Так как задержка расписания О была равна из этого следует, что перестановка не увеличивает максимальную задержку расписания. ■

Из этого немедленно следует оптимальность нашего жадного алгоритма.

(4.10) Расписание A, построенное жадным алгоритмом, обеспечивает оптимальную максимальную задержку L.

Доказательство. Пункт (4.9) доказывает, что оптимальное расписание без инверсий существует. С другой стороны, согласно (4.8), все расписания без инверсий имеют одинаковую максимальную задержку, так что расписание, построенное жадным алгоритмом, является оптимальным. ■

Расширения

Существует много разных обобщений задачи планирования. Например, мы предположили, что все задания были готовы к запуску, начиная с общего начального времени s. Естественная, но более сложная версия этой задачи содержит заявки i, которые, в дополнение к предельному времени d_i и запрашиваемому времени t_i, также содержат минимально возможное начальное время r_i. Самое раннее возможное начальное время обычно называется временем разблокировки. Задачи с временем разблокировки естественным образом встречаются в ситуациях с заявками вида: “Можно ли зарезервировать аудиторию для проведения двухчасовой лекции в интервале от 13 до 17 часов?” Наше доказательство того, что жадный алгоритм находит оптимальное решение, принципиально зависит от факта доступности всех заявок в общее начальное время 5. (А вы видите, где именно?) К сожалению, как будет показано далее в главе 8, для более общего варианта задачи найти оптимальное решение намного сложнее.