Norenkov.Osnovy.Avtomatizirovannogo.Proektirovania.2002 (525024), страница 46
Текст из файла (страница 46)
Требуетсяупаковать компоненты в контейнер с минимизацией высоты Язаполненной части контейнера (допускаются следующие ориентации компонентов: исходная соснованием, параллельным дну контейнера, повернутая на 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. Математическое обеспечение синтеза проектных решенийНачало исполнения алгоритма — включение в D, двух вершин kw.1, которымсоответствует минимальный элемент матрицы С.Поскольку в синтезируемой сети необходимо иметь резервные каналы наслучай выхода из строя основных, то в построенном каркасе устраняютсявисячие вершины путем их соединения между собой.
Для этого достаточнопостроить еще одно дерево, но уже на графе, включающем только висячиевершины. Таким образом, каркас будет содержать связи двух построенныхдеревьев.Алгоритм второй процедуры основан на классификации связей. Связи первого ранга — это связи каркаса. Связь второго ранга — это хорда (/, j), такая,что имеется вершина k и связи (/, К) и (k, j) включены в каркас. Хорда Р-торанга — это хорда (i, j), такая, что имеется вершина k и связи (г, К) и (k, j)являются связями ранта, меньше Р, причем одна из них имеет рант Р - 1.Результаты классификации хорд составляют матрицу U, ее элемент U = Р ,где Р , — ранг связи (г, j).Заполнение матрицы U происходит по следующему алгоритму. Сначала всемсвязям (i,j) первого уровня присваивается ранг Р = 1, т. е.
принимаем U — \.Далее, если U = О и имеется k >j, такое, что (Uik- I and Ujk=P) or (Uik = P andUk= 1) = true, то Ut := P + 1. Алгоритм выполняется при последовательномувеличении Р до полного заполнения U.Перенос трафика из хорд в связи каркаса происходит по эвристикам, выбираемым генетическим методом.
Начиная со связей высшего ранга и кончаясвязями ранга 2, последовательно к каждой связи (г, j) применяется одна изследующих эвристик:1) если (Uik= I and Uk= P -1) = true, то трафик из связи (/,_/) переносится всвязи (г, k) и (j,K);2) выбирается k, соответствующее минимальной сумме Cik+ С k при условии (Uik = P -\ and Uk= 1) = true; трафик из связи (г, j) переносится в связи (г,К)и (Д);3) то же, что и п. 2, но с измененным условием (Uik < Р - 1 and Uk<P-l) == true;4) то же, что и п. 3, но перенос трафика осуществляется только, если С >> Сл+ Cjk, иначе связь присоединяется к каркасу.В результате переноса трафика часть связей ликвидируется. Благодаря генетическому поиску, оставшаяся система связей и распределение в них трафика оказываются близкими к оптимальным.Упражнения и вопросы для самоконтроля1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
