Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Декомпозиционные приближенные алгоритмы оптимизации расписаний параллельной системы с задержками поступления заявок. Жадный алгоритм и бикритериальное приближение.

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

· Пусть все заявки упорядочены по возрастанию задержек и разбиты на Q непересекающихся подмножеств. Соответственно, переменные рассматриваются в рамках подмножества и шага алгоритма. Расписание на выходе системы по завершении обслуживания заявок из подмножества q является расписанием на входе системы для заявок из следующего подмножества. Каждая подзадача на любом шаге удовлетворяет следующим условиям:

· Используется булева переменная назначения заявки j на прибор i (1 — назначено, 0 — не назначено)

· Каждая заявка назначается только на один прибор.

· Количество назначений заявок на один прибор ограничено сверху и снизу. Нижнее ограничение — 0. Верхнее ограничение — оставшееся число не распределенных заявок (разность общего числа заявок и числа назначений, сделанных при решении задачи на текущем шаге для предыдущих подмножеств).

· Сумма задержек по расписанию заявок на приборе i ограничена сверху числом (и так для каждого прибора)

· Суммарная длительность обработки заявок на приборе i ограничена сверху числом (и так для каждого прибора), минимизируется

При решении задачи с данными ограничениями будет получено Парето-оптимальное множество решений (для данного подмножества заявок на данном шаге). По нему можно найти оценку фактической длины оптимального расписания. Для этого последовательно вычисляются (опять в рамках каждого подмножества на каждом шаге) с использованием редукции в ЗЛПБП:

1. Булевы переменные (заменяющие булеву функцию f, см. вопрос 3)

2. Переменные , имеющие смысл времени фактического ожидания заявкой j прибора i (см. вопрос 2). Вычисляются через булеву переменную u. Вводятся, если ориентировочная фактическая задержка получилась отрицательной.

3. Критерий

Таким образом, для каждого подмножества заявок будет найдена совокупность решений (состоящая из решений, найденных на разных шагах), надо будет найти приближение к оптимальному решению. Например, использовать жадный алгоритм. Алгоритм жадного алгоритма:

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

2. Формируем подзадачу для очередного подмножества q (ограничения сформированы выше 1.33-1.38). Находим Парето-оптимальное множество ее решений Далее перебираются все шаги, для каждого подмножества определяется минимальное значение (фактическая оценка локально наилучшего по всем приборам, шагам и заявкам из наборов назначений в рамках подмножества q). Ему соответствует и локально наилучший набор решений (назначений) для данного подмножества заявок.

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

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

6. Динамическое программирование с отсевом вариантов в оптимизации расписаний параллельной системы с задержками поступления заявок

ДП характеризуется разбиением на подзадачи. Решая поэтапно, мы освободимся от рекурсии. Время высвобождения прибора i для s-ого варианта решения на шаге q, также является фактической задержкой начала обслуживания прибором I заявок на подмножестве q+1, если задержка заявки на следующем этапе менее задержки на предыдущим этапе. Для любого q определим следующее отношение порядка

P-ое расписание предпочтительнее s-ого, если имеет меньшее врем завершения самой продолжительной операции для всех приборов. Для построения эффективного приближенного алгоритма воспользуемся общей схемой ДП, производя отсев локально наихудших вариантов на ряде шагов (этапов) динамического программирования.

- время завершения обслуживания прибором I заявки s на этапе s,

 

- минимальное время завершения обслуживания принятых заявок на всех этапах.

 

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

Рекуррентное соотношение Беллмана для этой задачи:

Где первое слагаемое – время обслуживания на этапе s, а второе — минимально возможное время завершения обслуживания предыдущих этапов. В свою очередь сумма является слагаемым для этапа s+1.

На последнем шаге следует выбрать минимальное значение время завершения обслуживания принятых заявок на всех этапах. В данном методе мы определим кол-во вариантов s, которые мы будем оставлять на каждом этапе для дальнейшего анализа. S=2^k, где k-некоторая константа.

Алгоритм:

1) Ввод исходных данных и параметра k

2) s=s+1

3) Проверка номера этапа, если s>J (кол-во заявок), переход к п.7, иначе след. Пункт

4) Генерируем все допустимые варианты расписаний, длины расписаний

5) Если N (число вариантов) <= S (который мы определили сами вначале), то переход к п.2, в противном случае след. Пункт.

6) Отсев половины вариантов с наибольшими длинами расписаний. Переход к п.2.

7) Выбор вариантов кратчайших расписаний. Составление расписаний обратным ходом ДП.

 


Последнее изменение этой страницы: 2016-06-09

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...