Эвристические алгоритмы для задач синтеза расписаний обслуживания

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

Следует указать две сферы приложений эвристических алгоритмов: 1) синтез расписаний приемлемого для практического использования качества; 2) получение нижних оценок, которые оказываются необходимыми для точного решения задач синтеза оптимальных расписаний методом ветвей и границ. Вторая сфера предполагает многократное использование эвристического алгоритма в процессе решения одной задачи; он должен обладать достаточным быстродействием, хотя получаемые оценки могут быть относительно грубыми.

В канонической модели однопроцессорного обслуживания заявки потока R = {1, 2,..., n } считаются пронумерованными в порядке их поступления (0 = t (1) ≤ t (2) ≤...≤ t (n)). Дополнительно полагаем, что заявки, поступающие на обслуживание одно-временно, получают очередные номера в порядке убывания показателя μ (i) = а (i)/τ (i).

Первый эвристический алгоритм тривиален, он основан на принципе «первый пришел – первым обслуживается» (ПП-ПО) Результатом применения алгоритма ПП-ПО, с учетом принятого способа нумерации заявок, всегда является расписание ρ = (1, 2,..., n). Как правило, более качественными оказываются расписания, конструируемые μ -алгоритмом, предусматривающим, что в каждый момент принятия решения по загрузке освободившегося процессора из совокупности ожидающих обслуживания выбирается заявка с наибольшим значением показателя μ = а (i) / τ (i).

Изложим идею следующего эвристического алгоритма, назовем его (p, q) - алгоритмом, здесь p и q – небольшие натуральные числа (n > p ≥ q). На первом этапе работы алгоритма рассматривается начальный отрезок входного потока (подпоток R ₁), содержащий заявки 1, 2,..., p. Любым точным методом, эффективно работающим благодаря выбранному небольшому значению параметра p, строится минимизирующая суммарный штраф последовательность π ₁ обслуживания заявок этого подпотока; начальный, длины q, отрезок последовательности π ₁ считаем начальным отрезком синтезируемого расписания обслуживания ρ * заявок исходного потока R = {1, 2,..., n }; заявки, нашедшие свое место в расписании ρ * из потока R изымаются, получаемый в результате поток обозначаем R ¹; момент завершения обслуживания заявок, входящих в построенную начальную часть расписания ρ * обозначим Т (ρ *, 1). На втором этапе заявки потока R ¹, поступившие не позднее момента Т (ρ *, 1), переупорядочиваются в порядке убывания значений показателя μ (i), получаемый поток обозначаем R ⁽¹⁾; далее рассматривается начальный отрезок потока заявок R ⁽¹⁾ (подпоток R ₂), содержащий p заявок; выбран; начальный, длины q, отрезок последовательности π считаем следующим отрезком синтезируемого расписания ρ * обслуживания заявок потока R; заявки, нашедшие свое место в расписании ρ * из потока R изымаются, получаемый в результате поток обозначаем R; момент завершения обслуживания заявок, входящих в построенную к данному моменту начальную часть расписания ρ * обозначим Т (ρ *, 2). На третьем этапе заявки потока R, поступившие не позднее момента Т (ρ *, 2), переупорядочиваются в порядке убывания значений показателя μ (i), полу-чаемый поток обозначаем R; далее рассматривается начальный отрезок потока R, содержащий p заявок, и т.д., вплоть до момента либо естественного завершения процесса, либо выполнения после некоторого k -го этапа условия Т (ρ *, k) ≥ t (n). При реализации последнего варианта заявки, не вошедшие в сформированную часть расписания, приписываются к ней справа в порядке убывания показателя μ (i).

Легко видеть, что верхней оценкой временной вычислитель-ной сложности изложенного алгоритма (с учетом сортировок) является Сn log₂ n, где С – не зависящая от n константа.

Существенна зависимость множителя С от выбора определяющих качество алгоритма значений параметров p и q. Пусть оптимальные решения получаемых частных задач с p заявками синтезируются методом динамического программирования. Тогда число элементарных операций, выполняемых при решении каждой частной задачи, прямо пропорционально р ²2 р. Общее число подлежащих решению задач с p заявками обратно пропорционально q. Получаем, что константа С прямо пропорциональна р ²2 ^р и обратно пропорциональна q. Чем больше значение p и меньше значение q, тем выше ожидаемое качество решения и тем больше трудоемкость алгоритма его синтеза.

Реально вместо изложенной канонической (p, q)-процедуры целесообразно применение ее естественных модификаций. Так в случае, когда на некотором k + 1-м этапе в совокупность рассматриваемых р заявок подпотока входят только уже поступившие заявки, а первая поступающая позднее момента времени Т (ρ *, k) заявка имеет большее значение показателя μ (i), то эту за-явку следует зачислить в число перспективных к включению на данном этапе.

Концепция (p, q)-алгоритма играет существенную роль и для периодов с относительно большим горизонтом планирования, когда точной может быть информация о моментах поступления только идущих вначале заявок, для последующих заявок моменты прибытия известны как ожидаемые средние значения. Тогда реализация этапов синтеза (p, q)-алгоритмом расписания обслуживания ρ * синхронизируется с поступлением уточненных данных о моментах прибытия последующих заявок. С учетом периодичности поступления таких данных выбираются значения параметров p и q.

Идея следующего эвристического алгоритма, именуемого алгоритмом вставки, тоже достаточно проста. На первом этапе определяем оптимальную последовательность π ₁ обслуживания заявок 1 и 2 в предположении, что других заявок нет; при этом подсчитываются суммарные штрафы по двум указанным заявкам для обеих возможных последовательностей их обслуживания. На втором этапе: если заявка 3 поступает ранее момента завершения обслуживания первой в π ₁ заявки, подсчитываются суммарные штрафы для трех последовательностей, получаемых из π ₁ приписыванием заявки 3 к π ₁ слева, справа и ее вставкой в промежутке между первым и вторым элементом этой последовательности; если заявка 3 поступает между моментами завершения обслуживания первой и второй заявки последовательности π ₁, суммарные штрафы подсчитываются для двух последовательностей, получаемых из π ₁ приписыванием заявки 3 справа и ее вставкой между двумя имеющимися элементами последовательности; если заявка 3 поступает не ранее момента завершения обслуживания второй заявки последовательности π ₁, справа. Через π обозначаем ту из последовательностей, для которой суммарный штраф минимален. При определении расположения произвольной заявки k составленную на предыдущем этапе последовательность π _k-2 разбиваем на две последовательные части π ′ _k-2 и π *_k-2, где π ′ _k-2 – максимально возможная по числу элементов начальная часть такая, что реализация расписания π ′ _k-2 завершается не позднее момента прибытия заявки k; далее из π _k-2 путем вставки заявки k на место между частями π ′ приписываем заявку 3 к π _{k- 2}, π * _{k –2} и на все места правее указанного получаем ряд последовательностей обслуживания; для каждой из полученных последовательностей вычисляем суммарный штраф, последовательность с минимальным значением суммарного штрафа обозначаем π _{k –1}. Итогом работы алгоритма является последовательность обслуживания π _{n –1}.

Оценка временной вычислительной сложности алгоритма вставки Сn ², где С – не зависящая от n константа.

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

Отметим возможность построения для канонической задачи однопроцессорного обслуживания алгоритмов локальной оптимизации. При этом k -окрестность произвольного расписания ρ образуют расписания, каждое из которых получается из ρ путем некоторого перераспределения мест между k заявками, в последовательности ρ идущими подряд. Начальный для процедуры локальной оптимизации вариант расписания может быть построен одним из ранее изложенных эвристических алгоритмов (например, (p, q)-алгоритмом или алгоритмом вставки).

Следует также отметить, что идеи, положенные в основу (p, q)-алгоритма и алгоритма вставки легко адаптируются для синтеза расписаний обслуживания потоков заявок в системах с параллельными и последовательными процессорами. Соответствующие вычислительные процедуры могут входить и как отдельные модули в алгоритмы более сложной структуры.

Сейчас рассмотрим сформулированную в гл. 2 задачу синтеза расписания обслуживания потока поступающих в дискретном времени заявок R = {1, 2,..., n } в системе, состоящей из m идентичных параллельных процессоров Π _j (j= 1, …, m). Для этой задачи в гл. 2 записаны рекуррентные соотношения динамического программирования, однако определяемый ими вычислительный процесс очень трудоемок и реально осуществим лишь при малом числе процессоров и небольшом количестве заявок в потоке. Основанная на декомпозиции эвристическая процедура состоит в последовательном выполнении двух этапов.

На первом этапе строится расписание обслуживания ρ ₀ – «нулевой» вариант искомого решения. При этом используется модифицированная на случай m параллельных процессоров многошаговая (p, q)-процедура, где p и q – относительно небольшие натуральные числа, q ≤ p < n. При реализации каждого шага этой процедуры с учетом того, что число p подлежащих обслуживанию заявок невелико, можно использовать метод динамического программирования.

В результате выполнении первого этапа мы получаем расписание ρ ₀, которое разделяет поток заявок R = {1, 2,..., n } на m подпотоков, заявки j -го подпотока должны обслуживаться процессором Π _j (j= 1, …, m).

Второй этап – построение расписания обслуживания ρ ₁ путем решения m канонических задач однопроцессорного обслуживания. В подлежащей решению j- ой задаче процессор П_j, должен обслужить заявки j -го подпотока, j=1, …, m. Для решения каждой из канонических задач в зависимости от ее размерности, а также требований к быстродействию и точности, может быть применен либо синтезирующий оптимальное решение метод динамического программирования, либо одна из перечисленных выше эвристических процедур.