Норенков И.П. - Основы автоматизированного проектирования (1060628), страница 45
Текст из файла (страница 45)
Так,в правиле Qt загрузка кластера будет оцениваться не его внутренним трафиком (связностью), а числом размещенных в нем элементов. Во всех правилахQk возможным кластером-кандидатом может быть только тот кластер, в котором еще не исчерпан лимит на размещение. Правила 5",- S3 используются безизменений. При вычислении целевой функции штрафы за нарушение ограничений не предусматриваются, так как учет ограничений введен в эвристики.Возможны и другие варианты множества эвристик.
Например, можно использовать правила, в которых очередным размещаемым элементом выбирается следующий элемент:£,) в строке которого в матрице связей находится максимальный элементматрицы;iS"2) имеющий максимальную суммарную связность с уже размещеннымиэлементами;7 Основы автоматизированногопроектирования1934. Математическое обеспечение синтеза проектных решенийS3) имеющий минимальную суммарную связность с еще не размещеннымиэлементами.Для выбранного по одному из правил S^- S3 элемента Р определяется кластер, в котором:Q}) имеется элемент, максимально связанный с Р',Q2) уже размещенные элементы максимально связаны с Р (максимальнасуммарная связность).Из этих правил можно скомбинировать шесть разных эвристик и добавитьэвристику, в которой сначала определяется кластер L по признаку минимальнойзагруженности, а затем для него выбирается элемент по признаку максимальной связности с уже размещенными в L элементами.
Ограничения на максимально допустимое число элементов в кластере введены в эвристики.Размещение двумерных разногабаритных компонентов. Эта задачаизвестна как задача размещения электронных компонентов (в кристаллах БИСили на печатных платах) или как двумерная задача упаковки грузов в контейнеры (в последнем случае ее часто обозначают 2DBPP (2D Bin Packing Problem)).Рассмотрим подход к ее решению с помощью НСМ.В этой задаче задана полубесконечная полоса (контейнер с открытым верхом и шириной W) и множество разногабаритных прямоугольных компонентоввысотой D и основанием шириной Z(, число компонентов равно N. Требуетсяупаковать компоненты в контейнер с минимизацией высоты Язаполненной части контейнера (допускаются следующие ориентации компонентов: исходная соснованием, параллельным дну контейнера, повернутая на 90°).При решении задача разбивается на подзадачи, в каждой из подзадач выбирается слева наиболее низкий незаполненный участок контейнера и выполняется его заполнение по одной из следующих эвристик:Э,) выбирается еще не размещенный компонент, обеспечивающий наименьший горизонтальный зазор gap>0 (рис.
4.14); если gap>0, то компонент размещается вплотную к тому краю участка, на котором меньше (по абсолютнойвеличине) вертикальный зазор г; если компонентов с gap>0 нет, то участокшириной а и высотой h объявляется пустотелым и заполняется фиктивнымкомпонентом;32) то же, что и в Э,, но выбирается компонент, обеспечивающий минимальный вертикальный зазор z при исходной ориентации компонента; если таких компонентов нет, то делаетсяпопытка найти подходящий компонент при повернутой ориентации;33) то же, что и в Э2, но сначала исследуютсяgapкомпоненты при повернутой ориентации;34) для очередного размещения выбираетсякомпонент с наибольшей площадью среди ещеРис. 4.14.
Размещение компо- не размещенных компонентов в случае положинента в очередном участкетельного зазора gap.1944 4 Методы структурного синтеза в системах автоматизированного проектированияСинтез расписаний. Задачи синтеза расписаний требуется решать вомногих приложениях, например при планировании различных производственных процессов, распределении ресурсов, выборе числа и типов процессоровдля многопроцессорных специализированных комплексов и т.
п.Рассмотрим постановку и подход к решению одной из основных разновидностей задач синтеза расписаний, обозначаемой JSSP (Job Shop SchedulingProblem). К исходным данным относятся:множество работ А = {АГ А2, ..., Ап};множество исполнителей, называемых также машинами (или серверами)М={М1,М2,...,Мт};матрица Р = [Ptj], где Ptj — затраты времени на выполнение работы Л ( намашине М;вектор С = (С,, С2, ..., Ст), где С — цена за единицу времени работы машины М;ограничения на время окончания работ Т = (Г,, Т2, ..., Гп), где Т— предельное время для завершения работы А:,штраф Q, добавляемый к общим затратам Z при нарушении какой-либо работой соответствующего ей временного ограничения.Необходимо составить расписание, при котором минимизируются затратына выполнение всех работ с учетом штрафов.В других разновидностях задач синтеза расписаний могут быть те или иныеусложняющие решение отличия.
Примерами отличий могут быть: 1) многостадийность — наличие нескольких стадий обслуживания каждой работы;2) разделение работ на несколько групп и учет дополнительных затрат на переналадку машин, требующейся при последовательном обслуживании работ разных групп; 3) частичная упорядоченность работ, т. е. для некоторых пар работAt и Ak введены ограничения видагде 5 — время начала 2-й работы; Ek — время окончания k-й работы.Каждая эвристика при применении для синтеза расписаний метода НСМвключает два правила: одно для выбора очередной работы, другое для выборамашины, обслуживающей эту работу.Например, при синтезе многостадийных расписаний в качестве очереднойможет выбираться работа: 1-е наименьшим Г; 2 — с наименьшим временемокончания обслуживания на предыдущей стадии Е. Примеры правил выборамашин: 1 — машина, на которой обслуживание данной работы будет наиболеедешевым; 2 — машина, на которой работа будет обслужена за наименьшеевремя.
Эти правила образуют четыре эвристики. Можно использовать дополнительные правила, например правило, учитывающее затраты времени на переналадку машин.'•1954. Математическое обеспечение синтеза проектных решенийМаршрутизация транспортных средств. Среди задач проектированиямаршрутов транспортных средств при перевозке различных грузов одной изнаиболее трудных для решения считается задача VRPTW (Vehicle RoutingProblem with Time Windows) - задача маршрутизации транспортных средств свременными окнами.
Временным окном здесь называют временной интервал,в который нужно выполнить заказ на перевозку. В задаче заданы:п — число узлов-потребителей продукта (k-й узел-потребитель отождествляется с k-м заказом);z — число узлов-источников продукта;т — число серверов (транспортных средств);w — общее число узлов;V — исходное расположение потребителей, источников и серверов в узлахтранспортной сети;D — матрица расстояний между узлами;Ть и T2i — нижняя и верхняя границы временного окна для выполнения /-гозаказа;р — число типов продукта.Кроме того, для узлов-потребителей и узлов-источников заданы объемысоответственно заказанного и имеющегося продукта каждого типа, для серверов — максимальный объем перевозимого продукта, скорость движения, ценаза единицу расстояния пробега, штрафы за нарушение временных ограничений(выход за пределы временных окон), причем штрафы зависят от цены единицыпродукта каждого типа и от степени нарушения ограничений.Требуется найти график движения транспортных средств для выполнениявсех заказов с минимальными затратами.Каждая эвристика при использовании НСМ включает в себя правила длявыбора заказа (узла-потребителя), узла-источника продукта и транспортногосредства (не исключено, что для выполнения конкретного заказа привлекаетсяболее чем по одному источнику и/или серверу).Для выбора узла-потребителя можно использовать следующие правила:5,) предпочтение отдается узлу с максимальным суммарным объемом заказанного продукта;S2) выбирается потребитель с максимальной ценой заказанного продукта;iS"3) выбирается потребитель с минимальной верхней границей временногоокна.В правилах выбора узла-источника продукта предпочтение может отдаваться источнику:£?,) с минимальным расстоянием до выбранного в первой части узла-потребителя;Q2) с минимальной суммой D расстояний до узла-потребителя и до ближайшего узла, в котором имеется свободный сервер;1964.4.
Методы структурного синтеза в системах автоматизированного проектирования23) с минимальным значением h = (Z,+ L2)U0/U, где Z, и L2 — расстояниясоответственно до узла-потребителя и до ближайшего узла, в котором имеется свободный сервер, U0— суммарный объем заказанного продукта, U— суммарный объем продукта в источнике.Эвристика дополняется правилом, в котором выбирается сервер:К,) с минимальным расстоянием до узла-потребителя;V2) с минимальным временем освобождения от предыдущего обслуживания;V3) с минимальным временем выполнения маршрута.Синтез топологии каналов передачи данных в вычислительныхсетях. Задачи определения топологии сетей различного рода и распределенияв них трафика относятся к сложным задачам структурного синтеза. Задачи,подобные описанной ниже задаче синтеза сети каналов передачи данных, встречаются во многих приложениях при синтезе сетей и распределения в них материальных, транспортных, информационных потоков.Рассмотрим следующую задачу.
Пусть дано:• множество Y узлов (вершин) сети, N— число узлов;• трафик, для его задания используется некоторая метрика; трафик задается в виде матрицы Т, ее элемент Т есть трафик между узлами i nj;• матрица С стоимостей прокладки и/или аренды (за прогнозируемое времяэксплуатации) связи между парами узлов, С — стоимость связи между узлами / и у;• стоимость обслуживающего оборудования, которая определяется типомоборудования, а тип выбирается в зависимости от трафика в соответствующем канале.Необходимо минимизировать общие затраты на построение сети, складывающиеся из затрат на прокладку и аренду связей и на обслуживающее оборудование.Решение задачи включает две процедуры: 1) выбор системы связей — каркаса сети; 2) перенос трафика связей, не вошедших в каркас и называемыххордами, в те или иные связи каркаса.В первой процедуре рассматривается полный граф G = {Y, S}, S — множество ребер (связей) полного графа.
Каркас выбирается в виде покрывающегодерева, в дальнейшем к нему могут добавляться некоторые другие связи.Алгоритм выбора дерева основан на последовательном подключении к подмножеству D( вершин, уже включенных в дерево, очередной вершины из подмножества D2 вершин, еще не включенных в дерево. Правило выбора подключаемой вершины — ее максимальная близость к дереву, т. е. в деревовключается связь (&,/) при условииСи = min W.Wт = min Сч1"je D,1974.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
