Структурный синтез и построение расписаний

План лекции. Классификация задач построения расписаний, возникающих при проектировании ИУС РВ. Алгоритмы имитации отжига. Генетические алгоритмы. Алгоритмы на основе схемы муравьиных колоний. Жадные алгоритмы. Алгоритмы, сочетающие жадные стратегии и стратегии ограниченного перебора.

Классификация задач построения расписаний Модель задается: моделью ресурсов моделью системы заданий (работ) способом задания расписания мерой оценки качества расписания ограничениями на корректность расписания моделью вычислений

Модель ресурсов В большинстве моделей ресурсы состоят просто из набора процессоров P. В наиболее общей модели еще имеется набор дополнительных типов ресурсов R, некоторое подмножество которых используется на протяжении всего времени выполнения задания на процессоре. Общее количество ресурса типа r i задается целым положительным числом. [Теория расписаний и вычислительные машины. Под ред. Э.Г. Коффмана. М.: Наука, с.] Разделяемые ресурсы: среда обмена и память.

Тип процессоров процессоры одинаковые по производительности и по функциональным возможностям; процессоры разные по производительности и одинаковые по функциональным возможностям; процессоры разные по производительности и по функциональным возможностям.

Модель системы заданий T={t 1,t 2,…,t n } - набор работ; отношение частичного порядка на T. Если работы связаны отношением t i t j,то работа t i должна быть завершена раньше, чем начнется выполнение работы t j ; – функция вычисления времени выполнения работы ; R={r 1 (t j ),…, r s (t j )} – набор, i-ая компонента которого задает количество ресурса типа r i необходимое для выполнения задания t j.

Тип отношения частичного порядка пустое, лес, произвольное.

Функция вычисления времени выполнения работы 1.Табличная функция. Времена могут быть: –различными, –равными, –равными 1 или 2. 2.Аналитически заданная функция. 3.Имитационная модель. 4.Эмулятор.

Директивные интервалы работ 1.f- общий директивный интервал для всей системы работ. 2.[s j,f j ) – индивидуальные директивные интервалы для каждой работы. 3.[0,f j ) – индивидуальные директивные интервалы с общей левой границей. 4.r j – требуемая частота выполнения работы. 5.(r j, φ 1, φ 2 ) – требуемая частота выполнения работы + фазовые сдвиги.

Расписание 1.Временная диаграмма – для каждой работы задано время начала выполнения s(t j ) и процессор на котором она выполняется. 2.Привязка работ к процессорам и порядковый номер выполнения работы на процессоре. 3.Привязка работ к процессорам и приоритет работы. 4.Статико-динамические расписания

PU1 PU2 время 1 67 PU1: PU2: PU1: PU2:

Мера оценки эффективности расписания 1.Время выполнения расписания. 2.Число используемых процессоров для выполнения множества работ за время не превышающее заданные директивный срок. 3.Максимальное число совместимых работ. 4.Критерии, основанные на использовании функций штрафа за нарушение директивных сроков работ.

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

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

Временные задержки учитываются временные задержки начала выполнения работ, определяемые: –отношением частичного порядка в расписании, – ограниченным числом процессоров; учитываются временные задержки начала выполнения работ, связанные с получением доступа к разделяемым ресурсам (каналам обмена, общей памяти….).

Итерационные алгоритмы построения расписаний Генетические и эволюционные алгоритмы Имитация отжига Алгоритмы локальной оптимизации f(HP) HP HP 1 HP 2 HP 3

Алгоритмы имитации отжига (принцип работы)

Алгоритмы имитации отжига (общая схема одной итерации) PU1: PU2: PU1: PU2: PU1 PU2 время HP= 2. f(HP)= 4. HP = 3. Проверка критерия останова 5. Выбор текущего приближения HP

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

Алгоритмы имитации отжига (система операций преобразования расписаний) 2 O1O1 O2O2 Теорема. Теорема. Для любых двух корректных расписаний HP 1 и HP 2 существует цепочка операций {O 1, O 2 }, переводящая расписание HP 1 в HP 2 так, что каждое промежуточное расписание корректно и длина цепочки

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

Алгоритмы имитации отжига (направленные стратегии применения операций) Стратегия уменьшения задержек. Утверждение. Если время начала выполнения каждой работы равно длине критического пути в графе потока данных, то расписание будет оптимальным. Стратегия заполнения простоев. Утверждение. Если простоев процессоров нет, то расписание будет оптимальным.

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

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

Генетические алгоритмы (операции скрещивания и мутации) бит инвертируется, если: FiFi FjFj 1L...

Генетические алгоритмы (схема пропорциональной селекции) 1.Вычислить среднее значение функции выживаемости для популяции. 2.Для i-ой строки популяции выделить 3.Из полученных строк сформировать новую популяцию.

Генетические алгоритмы (схема рулетки) 1.Вычислить среднее значение функции выживаемости для популяции. 2.Для i-ой строки популяции выделить сектор рулетки с центральным углом: 3.Сделать P запусков рулетки, где P – размер популяции. Каждый раз выделяем строке в чей сектор мы попали 1-го потомка. 4.Из полученных строк сформировать новую популяцию.

Генетические алгоритмы (теория схем) Почему ГА могут работать? Схема - представляет подмножество всех возможных строк, которые имеют те же самые биты в некоторых фиксированных позициях. Схема **000 представляет все строки с 0 в последних трёх позициях: 00000, 01000, и Схема 1*00* представляет строки: 10000, 10001, и Каждая строка представленная схемой называется примером схемы.

Генетические алгоритмы (теория схем) 1.Количество фиксированных позиций в схеме - это её порядок (**000 имеет 3 порядок): 2.Определяющая длина схемы - это расстояние между самыми дальними фиксированными позициями: у схемы **000 определяющая длина равна 2, у схемы 1*00* - равна 3.

Генетические алгоритмы (теорема схем, гипотеза строительных блоков) - ожидаемое количество примеров схемы h на шаге t+1 - средние значение целевой функции в популяции на шаге t - среднее значение целевой функции схемы h на шаге t

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

Муравьиные алгоритмы (МА для решения задачи коммивояжера) Общая схема итерации: «Создание» муравьев Построение маршрутов муравьями Обновление феромонного следа на найденных маршрутах

Муравьиные алгоритмы (построение маршрута и обновление феромонов) ii j

Муравьиные алгоритмы (использование для построения расписаний) Построение маршрутов Построение расписаний по маршрутам Обновление феромонного следа Вычисление целевых функции останов? нет да

Конструктивные алгоритмы построения расписаний Жадные алгоритмы Метод ветвей и границ Алгоритмы сочетающие жадные стратегии и стратегии ограниченного перебора t t t 1 6 7

Жадные алгоритмы (общая схема) Разложимые функции: 1.Выбрать очередную работу переменную x или у. 2.Выбрать в соответствии с локальной функцией (f 1,f 2 ) место размещения работы присвоить значение переменной.

Жадные алгоритмы (построение расписания выполнения работ в одноприборном устройстве) Для частной задачи: известен оптимальный жадный алгоритм сложности O(nlog n).

Жадные алгоритмы (GrA - алгоритм построения расписания для одноприборного устройства) 1.Упорядочиваем работы по возрастанию f j. Заявки с одинаковым значением f j располагаем в произвольном порядке. Сложность - O(nlog n). 2.Размещаем в расписание работу j=1. 3.Ищем первую работу для которой s i f j, размещаем ее в расписание и j=i. 4.Шаги 2, 3 повторяем пока список не исчерпан. Количество повторов - O(n).

Жадные алгоритмы (оптимальность алгоритма GrA) Теорема. Алгоритм GrA включает в расписание наибольшее возможное количество совместимых работ. Доказательство. Если в каком-то оптимальном расписании работа 1 отсутствует, то можно в нем заменить заявку с самым меньшим f на работу 1. Не нарушится совместимость работ и не изменится их количество в расписании.

Жадные алгоритмы (оптимальность алгоритма GrA) Т.е. можно искать оптимальное расписание содержащее работу 1 существует оптимальное расписание, начинающееся с жадного выбора. Из исходного набора можно удалить все работы несовместимые с 1. Задача сводится, к выбору набора работ из множества оставшихся работ, т.е. мы свели задачу к аналогичной задаче с меньшим числом работ. Рассуждая по индукции, получаем, что делая на каждом шаге жадный выбор, мы придем к оптимальному расписанию.

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

Алгоритмы сочетающие жадные стратегии и стратегии ограниченного перебора Выбор очередной работы(k1) Построение мн. допустимых мест (А) для размещения работы в расписание А=0 Разместить работу в расписание Выбор места размещения (k2) Вызов процедуры ограниченного перебора нетда

Пример процедуры ограниченного перебора О Пр1Пр2Пр3