Алгоритм парных перестановок для решения задач оптимизации компоновки и размещения элементов РЭС: Учебное пособие, страница 3

При конструкторском проектировании РЭА решаются задачи, связанные с поиском наилучшего варианта конструкции, удовлетворяющего требованиям технического задания и максимально учитывающего возможности технологической базы производства. Тесная взаимосвязанность задач и большая размерность каждой из них обычно не позволяют предложить метод поиска оптимального конструктивного решения в едином цикле в связи с трудностями создания общей математической модели, комплексно учитывающей особенности конструкторско-технологической базы производства. Поэтому в настоящее время осуществляется разработка и реализация алгоритмов решения отдельных задач этапа: покрытия, компоновки, размещения, трассировки [1]. В этой главе рассматриваются идеи, положенные в основу методов алгоритмизации типовых задач конструкторского проектирования, приводятся краткие описания широко применяемых на практике алгоритмов и обсуждаются возможности и особенности их использования в автоматизированных системах проектирования РЭС.

1.2. Компоновка конструктивных элементов

по коммутационным платам

Функционально-узловой метод проектирования предусматривает расчленение РЭА на отдельные конструктивно законченные единицы (модули) различных уровней: стойки, блоки, субблоки, функциональные узлы. В связи с этим при разработке конструкции РЭА проектировщик неизбежно сталкивается с задачей распределения элементов схемы (модулей предыдущего уровня) по коммутационным платам (коммутационным пространствам) данного уровня иерархии. При ее решении основным критерием оптимальности компоновки модулей является минимизация числа межмодульных связей, что необходимо для повышения надежности схем (за счет уменьшения числа разъемных соединений), уменьшения влияния наводок и времени задержки сигнала в цепях (вследствие минимизации суммарной длины соединений), упрощения конструкции и повышения технологичности разрабатываемого устройства [1,2].

Для построения формальной математической модели компоновочных задач удобно использовать теорию графов. При этом электрическую схему интерпретируют ненаправленным мультиграфом, в котором каждому конструктивному элементу (модулю) ставят в соответствие вершину мультиграфа, а электрическим связям схемы — его ребра. Тогда задача компоновки формулируется следующим образом. Задан мультиграф G(X,U). Требуется «разрезать» его на отдельные куски G1(A1,U1), G2(X2,U2),..., Gk(Xk, Uk) так, чтобы число ребер, соединяющих эти куски, было минимальным.

Конструктивными ограничениями в задачах компоновки являются:

число кусков разрезания графа k; число вершин в каждом из кусков графа (определяется числом конструктивных элементов, которые необходимо разместить на коммутационной плате, пластине БИС, подложке БГИС и т.д.);

максимальное число внешних связей каждого отдельно взятого куска графа (определяется количеством контактов используемого разъема, числом выводов стандартного корпуса БИС или БГИС); требование на раздельную компоновку отдельных вершин х_i, х_j Î Х в различных кусках графа (обусловлено конструктивными соображениями и условиями электромагнитной совместимости).

Известные алгоритмы компоновки можно условно разбить на пять групп [1]:

1) алгоритмы, использующие методы целочисленного программирования;

2) последовательные алгоритмы;

3) итерационные алгоритмы;

4) смешанные алгоритмы;

5) алгоритмы, основанные на методе ветвей и границ.