Содержание к диссертации
Введение
1. Анализ алгоритмов компоновки ТС АСУ 7
1.1. Постановка задачи и критерии компоновки ТС АСУ 10
Выводы 15
2. Общая характеристика алгоритмов компоновки ТС АСУ 16
Выводы 32
3. Алгоритмы оптимизации исходных схем соединений элементов в ТС АСУ 35
3.1. Алгоритм оптимизации исходной схемы соединений путем минимизации числа ребер получаемого графа 36
3.2. Алгоритм оптимизации исходной схемы соединений путем увеличения диаметра получаемого графа 44
3.3. Алгоритм оптимизации исходной схемы соединений путем уменьшения среднеквадратичного разброса степеней вершин получаемого графа 50
Выводы 57
4. Разбиение графа схемы соединений на части 58
4.1. Определение степени близости расположения вершин на графе 59
4.2. Последовательно-параллельный алгоритм разбиения графа, использующий матрицу отдаленностей 63
Выводы 68
5. Результаты экспериментальных исследований и программная реализация разработанных алгоритмов 69
5.1. Экспериментальная оценка качества алгоритма, использующего матрицу отдаленностей 69
5.2. Программная реализация процедуры компоновки, редактор принципиальных схем FreeStyle Schematic 94
5.3. Пример компоновки элементов схемы в узлы (разрезание схемы) в редакторе FreeStyle Schematic 95
Выводы 100
Заключение 101
Литература 102
Приложение 109
- Постановка задачи и критерии компоновки ТС АСУ
- Алгоритм оптимизации исходной схемы соединений путем минимизации числа ребер получаемого графа
- Определение степени близости расположения вершин на графе
- Экспериментальная оценка качества алгоритма, использующего матрицу отдаленностей
Введение к работе
Актуальность работы. Развитие автоматизированных систем управления (АСУ) специального назначения характеризуется постоянным усложнением решаемых задач, расширением выполняемых функций, а также разнообразием условий эксплуатации, чго реально предъявляет жесткие требования к техническому обеспечению АСУ в части живучести, надежности и качества.
По уровню организации разработки, масштабам проскіирования, производства и эксплуатации АСУ специального назначения являются одними из самых сложных технических систем, созданных человечеством. Общий срок разработки составляет 7-Ю лет, а период эксплуатации достигает 20 и более лет. В разработке, изготовлении и эксплуатации участвуют десятки специализированных научно-исследовательских и промышленных предприятий.
Технические средства (ТС) современных АСУ специальною назначения характеризуются рядом особенностей, существенно влияющих на организацию процессов их разработки. К ним относятся:
Высокие требования к надежности, качеству и унификации, определяемые большим сроком эксплуатации.
Воздействие широкого спектра дестабилизирующих факторов, определяемых условиями функционирования в динамически изменяемой внешней среде.
Широкое применений отечественной и зарубежной элементной базы, не отвечающей требованиям современных стандартов но стойкости к внешним воздействиям.
4. Высокие функциональные и массогабаритные показатели.
Сложность учета перечисленных особенностей определяет не только
длительность создания опытных образцов ТС АСУ специального назначения, но и многочисленные доработки по результатам изготовления, испытаний и запуска в серийное производство.
Сокращение сроков проектирования до определенных пределов при использовании традиционных ручных методов возможно за счет увеличения численности конструкторов и разработчиков. Однако при этом снижается удельная производительность труда из-за трудностей, возникающих при управлении, и ошибок, неизбежных при ручном проектировании (эти ошибки часто 'обнаруживаются уже в процессе производства, а даже небольшие коррекции в документации требуют разработки новых чертежей, объем которых сравним с основным объемом документации). Кроме того, число людей, занятых в сфере конструкторского проектирования, ограничено.
Ускорить и удешевить работы по ртс^у^'у "'"' 'Г "Г " "тир'"""""''
можно путем разработки формальнфхРЦ&#то*ггмта|фй1х) { методов и
CJ О»
создания на их основе программных средств математического моделирования.
Эффективное решение задачи компоновки ТС АСУ позволяет повысить надежность и качество ТС АСУ, а также существенно улучшить функциональные и массогабаритные показатели. Поэтому вопросы, связанные с разработкой формальных методов компоновки ТС АСУ специального назначения, являются весьма актуальными.
Актуальность работы подтверждается проведением НИР и ОКР в рамках программ:
федеральная целевая программа «Российские верфи»;
федеральная программа «Российская электроника»;
межотрослевая программа «Координация деятельности в области промышленной автоматизации и системостроения».
Цель работы и задачи исследования. Целью диссертационной работы является разработка методов и программных средств решения задачи компоновки ТС АСУ.
В соответствии с этим в работе ставились и решались следующие задачи;
- анализ методов компоновки ТС АСУ, формирование объективной
оценки качества результата;
-разрабоїка методов оптимизации формальных описаний схем соединений;
- нахождение качественного параметра, характеризующего степень
связности элементов в схеме соединений;
- разработка эффективного метода компоновки ТС АСУ;
-создание программных средств автоматизированной компоновки
ТС АСУ
Меюды исследования. Для решения поставленных задач широко использовались аппараты теории графов, теории множеств, векторной алгебры и аналитической геометрии, методы оптимизации на графах, а также общие вопросы теории и методов конструирования и технологии произволе іва ТС АСУ.
Научная повніші диссертационной работы:
раїрабогка моделей коммутационных схем, решающих проблему неопределенное!и соединений в пределах электрической цепи;
определение качесівенною параметра, характеризующего степень связное і и )леменюв в пределах создаваемого узла;
разработка эффективного алгоритма компоновки ТС АСУ.
Нрактчсскаи ценность диссертационной работы заключается в соід.иіни чеюдики автоматизированной компоновки ТС АСУ и ее реализации и виде программного продукта, написанного на языке C++
Внедрение. Результаты диссертационной рабо і ы и «йде программного продукта i-recStyie Schematic используются для со «Дания схем электрических принципиальных в ОАО «Техирибор» и ФГУМ ЦНИИ «Морфизприбор». Кроме того, программой пользуются ряд частых лиц. Результаты диссертационной работы используются в учебном процессе Северо-Западного государственного заочного технического уииверсиїеіа.
Апробация работы Основные положения диссер і анионной рабо і ы докладывались и обсуждались на 51-ой научно-технической конференции студентов и аспирантов ГУТ, г. Санкт-Петербург, 1997 г; 53-ой научно-технической конференции студентов и аспирантов ГУТ, г. Санкт-Петербург, 1999 г; 53-ой научно-технической конференции профессорско-преподавательского состава, научных сотрудников и аспирантов ГУТ, г. Санкт-Петербург, 2000 г; П-ой международной научно-технической конференции студентов, аспирантов и молодых специалистов стран СНГ, г. Санкт-Петербург, 2000г; Юбилейной научно-технической конференции «Связисты СПб ГУТ н телекоммуникации XXI века», г. Санкі-Пеїербурі, 2000г; Ш-ой международной научно-технической конференции сгудснюи, аспирантов и молодых специалистов стран СИГ, г. Одесса, 2001 г; 55-ой научно-технической конференции студентов, аспирантов и молодых специалистов ГУТ, г. Санкт-Петербург, 200] г.; IV-ой международной научно-практической конференции "Современные информационные и электронные технологии", Одесса, 2003г.; 1-ой научно-технической конференции молодых специалистов ФГУП ЦНИИ "Морфизприбор", Санкт-Петербург, 2003г.
Публикации. По материалам диссертации опубликовано 9 печатных работ, из них: монография, учебное пособие, одна статья в научно-техническом сборнике и тезисы шести докладов на научно-технических конференциях.
Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения и списка литературы, включающего 81 наименование. Основная часть работы изложена на 107 страницах машинописного текста, содержит 18 рисунков и 8 таблиц.
Постановка задачи и критерии компоновки ТС АСУ
Современное сложное ТС АСУ состоит из десятков и даже сотен тысяч элементов. Создание такого ТС АСУ в виде единого узла было бы не рентабельно: низкая надежность и ремонтопригодность, проблемы соблюдения тепловых режимов, электронная и магнитная несовместимость элементов и т. д. Поэтому такие ТС АСУ целесообразно создавать в виде нескольких связанных друг с другом узлов.
Процесс распределения элементов в узлы с учетом установленных критериев и ограничений принято называть компоновкой [8, 23, 27, 31, 38,44,55]. Среди задач компоновки можно выделить два характерные класса. К первому относятся задачи, в которых осуществляется распределение элементов в узлы с учетом таких ограничений как: - количество элементов в узлах; -число внешних выводов на узлах; -суммарная площадь, занимаемая элементами и соединениями и т. д. Главными критериями для такого распределения являются: -минимум числа образующихся узлов; - минимум числа межузловых соединений или внешних выводов на узлах; - максимум однотипности образующихся узлов (под однотипными узлами понимаются узлы, имеющие одинаковый состав и одинаковую схему соединений).
К отмеченным выше критериям могут быть добавлены и другие. Например, в ряде случаев при распределении особое внимание должно быть уделено определенным соединениям. Это, прежде всего, касается минимизации задержек в распространении сигналов. Как правило, переход соединительных цепей с одного уровня на другой влечет за собой уменьшение быстродействия схем или необходимость введения усилительных каскадов. Поэтому при распределении целесообразно локализовать некоторые цепи в пределах одного узла, например, цепи обратных связей в логических схемах. С другой стороны, определенные сигналы должны быть доступны для контроля неисправностей и поэтому, иметь внешние выводы.
Таким образом, к первому классу задач можно отнести задачи, в которых критерии оптимизации и ограничения могут быть сведены к определенным конструктивным параметрам расположения отдельных элементов и их межсоединений.
Второй класс образуют задачи, состоящие в распределении элементов в типовые узлы из заданного набора. Каждый из типовых узлов включает один или несколько элементов, в общем случае соединенных между собой. В качестве ограничений в задачах такого рода выступают: - количество элементов в узлах; -число внешних выводов на узлах и т. д. Основными критериями для такого распределения являются: -минимум числа используемых узлов; -минимум числа межузловых соединений; -минимум числа неиспользованных элементов в узлах. Применение алгоритмических методов для решения таких задач предполагает использование различных способов формального описания схем соединений. Схема соединений (монтажная) (ГОСТ 2.701-84) - это схема, показывающая соединения основных частей изделия (установки) и опреде 12 ляющая провода, жгуты, кабели или трубопроводы, которыми осуществляются эти соединения.
Любая схема соединений состоит из набора базовых элементов, определенным образом связанных между собой.
Среди различных вариантов формального описания монтажных схем наибольшей общностью и наглядностью обладает описание схемы в виде графа [13, 15, 36, 66, 67]. Такое представление широко используется при математической постановке различных оптимизационных задач конструкторского проектирования и позволяет в целом ряде случаев найти адекватные задачи в теории графов и воспользоваться при разработке алгоритмов решения задач конструкторского проектирования известными математическими методами.
С точки зрения теории графов, любое монтажное соединение группы выводов должно быть связным графом, множество вершин которого включает данную группу выводов. В понятии графа существен только факт присутствия ребер между отдельными вершинами, а не способ их изображения. Так, одному и тому же графу могут соответствовать различные чертежи, отличающиеся расположением вершин и геометрической формой соединяющих эти вершины ребер.
Расчет оптимальных конфигураций соединений составляет основу для разработки монтажных схем [2, 25, 51, 58].
Существенный недостаток большинства представленных в литературе методов формального описания схемы заключается в том, что в них не учитывается фактор неизвестности связей в пределах каждой много контактной цепи (такие цепи описываются полными графами). Решение практических задач показывает, что такое излишнее усложнение описания может привести к чрезвычайно сложным вычислительным процедурам и к большим затратам машинного времени, неоправданным с точки зрения конечного результата.
Целесообразно представлять многоконтактные цепи связными графами без циклов или «деревьями», так как такое описание сохраняет все
П преимущества предыдущего метода, а вместе с тем имеет в — раз меньше ребер. Основная сложность - выбор одного из П " покрывающих деревьев для каждого полного подграфа.
Наиболее распространенная схема решения задачи компоновки - последовательное заполнение узлов, а затем осуществление парных или групповых обменов между узлами до достижения экстремума (обычно локального) [1, 43, 52]. Отметим, что в общем случае задача многоэкстремальна, т.е. существует некоторое множество вариантов распределения элементов по узлам с минимальным числом внешних соединений, причем эти варианты могут иметь существенно различную топологию и, как следствие, существенно различные результаты решения последующих задач размещения компонентов и трассировки соединений.
При последовательном заполнении узлов используются локальные характеристики (максимальная конъюнкция, минимальная дизъюнкция), дающие информацию лишь об окрестности вершины или группы вершин. В большинстве случаев возникает проблема выбора из множества вариантов. Так, например, если множество однотипных вершин образует несвязный подграф, то общепринятые критерии не дают оснований для предпочтения при назначении элементов в узлы, т.е. выбор осуществляется произвольно. Неоднозначность существует и в случае, если число общих между парами элементов связей одинаково. В этом случае для получения оптимального решения необходимо организовывать поиск с возвращением, при этом комбинаторная сложность растет с увеличением глубины поиска.
Наиболее простой способ определения степени близости вершин на графе - определение кратчайшего пути между ними. Найдя кратчайшие пути между парами вершин, можно построить матрицу расстояний. Эта матрица содержит информацию для распределения элементов, не имеющих непосредственной связи. Однако матрица расстояний не несет информации в явном виде о степени связности графа и его частей, о числе путей различной длины между вершинами.
Алгоритм оптимизации исходной схемы соединений путем минимизации числа ребер получаемого графа
Необходимо определить такое минимальное дерево на графе, которое бы реализовывало все присутствующие цепи. Рассмотрим алгоритм построения минимального дерева графа. 1. Анализируя матрицу инцидентности можно еще до начала основной части алгоритма упростить поставленную задачу. Речь идет о следую т щих свойствах цепей (цепь - совокупность ребер, например Gt — Yu ): k=n а) если цени G/ и G/ равны, одну из них можно исключить из дальнейшего рассмотрения, увеличив вес ребер дерева оставшейся цепи. : 7 б) если некоторая цепь Gv равна совокупности цепей G/ ---Gj, то есть YG,=GV (3.1.1) /-і то ее так же можно исключить из дальнейшего рассмотрения, увеличив вес соответствующих ребер деревьев в цепях G/ ... Gj. 2. Оставшиеся после обработки исходной матрицы инцидентности цепи упорядочиваются по возрастанию их мощности (мощность цепи число элементов входящих в нее), то есть G, G-, ... GW. 3. Поскольку сложность определения дерева для той или иной цепи напрямую зависит от ее мощности (чем меньше мощность цепи, тем меньше вариантов реализации дерева для нее) целесообразно сначала рас смотреть цепи меньшей мощности. Более того, целесообразно образовать некоторый комплекс из цепей минимальной мощности, имеющих по одной общей вершине. Если возникает возможность образования нескольких комплексов, включающих разные цепи минимальной мощности, то среди них выбирают комплекс, содержащий большее число элементов (в идеале желательно, чтобы был получен связный граф, включающий все элемен ты). Если и при этом остается более одного кандидата, то выбор делается произвольно. 4. Выбирается первая цепь G/, входящая в комплекс и строится вспомогательная матрица инцидентности строки и столбцы, которой пред ставлены соответственно элементами, входящими в состав цепи G/ и це 38 пями Gj, Gk, ..., Gj, ..., G„„ имеющими в своем составе эти элементы.
При чем должно выполняться условие I Gj C\Gj 2. Если дерево цепи G,- может быть полностью реализовано ребрами деревьев цепей Gk, ..., Gj, ..., Gm, то при критерии минимума числа ребер графа для цепи Gj необходимо выбирать такие ребра, которые являются общими для двух цепей Gj и Gj, тем самым мы одновременно будем определять и фиксировать и ребра для дерева цепи G, и часть ребер деревьев цепей Gj.
Іісли дерево цепи Gj не может быть полностью реализовано деревьями цепей Gk ...Gm, то все вышеизложенное можно применить уже к отдельной цепи Gj и конкретно для нее решить задачу нахождения минимального дерева.
После выбора деревьев для первой цепи комплекса, осуществляется выбор деревьев для остальных цепей комплекса, а за тем и остальных цепей в возрастания их мощности. При определении деревьев для остальных цепей, необходимо учитывать число уже зафиксированные для них ребер на этапе оптимизации комплекса и сначала рассматривать максимально реализованные цепи.
Если в итоге остались цепи Gj имеющие менее 2-х общих вершин с образованным деревом, то в таких случаях нет необходимости рассматривать все возможные деревья для каждой из цепей, а достаточно произвольно выбрать по одному дереву для них.
Дерево цепи Gb может быть полностью реализовано ребрами деревьев цепей Gc и Gj. Выбираем и фиксируем ребра 3-4 и 4-5, то есть на данном шаге полностью реализованы деревья цепей G/,, ребро 3-4 дерева цепи Gc, а с учетом того, что на предыдущем шаге было зафиксировано ребро 1 -4 дерева этой цепи, то и она так же полностью реализована, и ребро 5-4 дерева цепи G(J.
Для таких классов элементов можно зафиксировать порядок их соединения и без ущерба исключить связи между несмежными элементами. Произведя подобные операции на всем множестве элементов, получим модель электрической схемы, которая не содержит полных подграфов каждой из цепей и для которой компактное размещение сильно связанных подграфов будет служить предпосылкой для трассировки с минимальным числом потенциальных пересечений проводников и минимальной длиной межсоединений.
Воспользуемся алгоритмом линейного размещения [9, 16, 18, 26, 34, 37, 61] , но не для решения собственно задачи размещения, а для повышения степени адекватности теоретико-графовой модели схемы, используемой на этапе компоновки. Применяя затем традиционные алгоритмы для компоновки элементов на основе уточненной модели, нетрудно обеспечить условия для качественного размещения и трассировки.
3. В матрице инцидентности выделяются колонки элементов, соединенных цепью максимальной мощности G/.
4. Строится дополнительная матрица инцидентности графа, соответствующего выделенным колонкам, и производится линейное размещение элементов графа по критерию максимального числа связей между соседними элементами (этим критерием можно обосновать необходимость использования методов линейного размещения). Для этого используется алгоритм [12, 14].
5. Строится матрица смежности для подграфа, полученного на предыдущем шаге, при чем учитываются только связи между смежными элементами.
6. Цепи, для которых число связываемых элементов в данном подграфе равно числу элементов в исходном графе можно исключить из дальнейшего рассмотрения, так как они являются зависимыми.
7. Для оставшихся независимых цепей повторяются пункты 2-6. Рассмотрим пример. Рассмотрим метод построения модели на примере, приведенном в предыдущем параграфе.
Для того, что бы минимизировать число звеньев покрывающего дерева для цепей, соединяющих некоторый элемент X. с другими элементами, необходимо и достаточно расположить рядом с этим элементом минимальное множество элементов, содержащих все внешние связи данного элемента. Очевидно, что если минимально число внешних связей для любого из элементов, размещенных на плате, то минимально и общее число звеньев общего дерева. Исходя из этого, можно исключить избыточные ребра графа, решив для каждого из элементов задачу выбора наименьшего числа их внешних связей и построить матрицу смежности графовой модели схемы.
Поскольку при реализации связей некоторого элемента множеством связей других элементов последние оказываются "частично реализованными" и притом, возможно, не оптимально, то необходимо установить критерий для определения последовательности решения этой задачи. Очевидно, что сначала необходимо реализовать связи наиболее "критичных" элементов, т.е. таких, для которых вероятность реализации связей некоторой группой случайным образом выбранных связей элементов минимальна.
Определение степени близости расположения вершин на графе
Математические модели М$ удобно использовать при реализации волновых алгоритмов трассировки. С увеличением числа элементов и контактов сложность М$ резко растет.
Основное преимущество А/с, - полная адекватность с схемой соединений в отношении планарности. Если М(» планарна, то всегда планарна схема соединений, и наоборот, если М не планарна, то не планарна и схема соединений. Основной недостаток Мс - резкое увеличение числа вершин и ребер графа по сравнению с ранее рассмотренными математическими моделями, особенно но сравнению с Mi Математическая модель M-j эффективно используют для решения задач распределения, размещения и после модификации планарности и трассировки. Основное преимущество - возможность задания изменяющейся информации цепях схемы соединений, которые конструктивно могут быть представлены любым из П{ "покрывающим деревом.
Математическая модель М% удобна для трассировки и размещения элементов, позволяет экономить оперативную память ЭВМ, но требует предварительной нумерации цепей.
Математическая модель Му является модификацией M-j, но в отличие от нее более наглядна, особенно с увеличением числа вершин и ребер. Заметим, что множество внутренних контактов схемы соединений можно разбить на отдельные функциональные группы, каждая из которых выполняет различные функции. Это позволяет выделять функционально неразличимые (инвариантные) контакты, что дает возможность осуществлять перекоммутацию цепей схемы и улучшать результаты размещения и трассировки соединений. 50
3. Главными достоинствами последовательных алгоритмов распределения (алгоритм Селютина, алгоритм Вернадского, алгоритм Кодре-са и т. д.) является их скорость и простота реализации. Кроме того, они позволяют легко учитывать дополнительные ограничения на распределение: несовместимость отдельных элементов в узле, априорно заданное функциональное распределение некоторых элементов схемы и др. Основным недостатком этих алгоритмов является локальный пошаговый характер оптимизации, приводящий к тому, что в начале процесса выделяются сильно связанные группы элементов, в то время как в последние узлы попадают малосвязные или вообще несвязные элементы. Это приводит при жестком ограничении на число выводов к увеличению числа узлов.
В параллельно - последовательных алгоритмах распределения (алгоритм с повторением элементов, алгоритм выделения узлов с минимальным числом внешних соединений, алгоритм формирования однотипных узлов и т. д.) в определенной мере устранен главный недостаток последовательных алгоритмов. Предварительное выделение набора групп элементов, обладающих существенными для конкретной задачи свойствами (число внешних соединений, внутренняя связность, функциональная завершенность), позволяет обеспечить более равномерное распределение элементов по узлам, а в ряде случаев приводит к значительно лучшим по качеству решениям.
Итерационные алгоритмы (алгоритм распределения, использующий числа связности, методы групповых перестановок и т. д.) обладают тем несомненным преимуществом, что они всегда обеспечивают получение результата, не уступающего начальному варианту распределения, и применимы при различных критериях оптимизации. Основным недостатком итерационных алгоритмов является значительное время отыскания локального оптимального решения, особенно если начальный вариант распределения имеет низкий показатель качества.
Экспериментальная оценка качества алгоритма, использующего матрицу отдаленностей
Алгоритмы и модели, полученные в результате работы, были использованы при создании программного средства разработки принципиальных схем FreeStyle Schematic.
Система FreeStyle Schematic предназначена для графического ввода принципиальных схем; создания библиотек символов элементов, на основе которых и строятся схемы и компоновки элементов схемы в узлы.
Помимо стандартных функций рисования и редактирования, предоставляемых большинством современных схемотехнических редакторов, предлагаемый редактор обладает следующими отличительными особенностями: - автоматическое размещение и трассировка принципиальной электронной схемы на базе описания Netlist и PDIF-, SPICE-форматов; - импорт/экспорт PDIF-, SPICE-файлов; - автоматическая генерация символов элементов принципиальных схем в стандартах ГОСТ и ANSI с автоматизированным занесением данных об образе "посадочного места" на печатной плате; - документирование схемы (оформление схемы в документ, соответствующий ГОСТ): автоматический выбор формата листа, добавление рамки, штампа и его заполнение; - поддержка иерархии (создание подсхем элементов).
Рассмотрим подробно процесс компоновки элементов схемы в узлы. 5.3. Пример КОМПОНОВКИ элементов схемы в узлы (разрезание схемы) в редакторе FreeStyle EDA
Одним из важнейших факторов, определяющих качество компоновки, является уменьшение числа внешних связей узлов.
Исходной для решения задачи компоновки является электрическая принципиальная схема. Поскольку в основе программы FreeStyle Schematic лежит последовательно-параллельный алгоритм, реализующий функции распределения, основным достоинством которого является равномерность заполнения образующихся узлов, то в качестве ограничений учитывается только число образующихся узлов.
Ниже приводятся 2 примера устройств, компановка которых была осуществлена с помощыомного средства FreeStyle Schematic с улучшением мас-согабаритных и функциональных показателей.
1. На основании проведенных исследований можно утверждать, что разработанный последовательно-параллельный алгоритм компоновки ТС АСУ, в основе которого лежит параметр отдаленности, позволяет получать качественные результаты как в случаях с сильно связанными группами элементов в исходной схеме соединений, так и в схемах с минимальным среднеквадратичным разбросом степеней вершин и с большим диаметром.
2. Реализованная в редакторе принципиальных схем FreeStyle Schematic функция компоновки позволяет разбивать схемы на заданное число частей, минимизируя при этом число связей между образующимися узлами.
3. Имена цепей, соединяющих элементы, расположенные в различных узлах, задаются с помощью портов. Редактор автоматически именует такого рода цепи, при выполнении процесса компоновки.
Основные теоретические и практические результаты диссертационной работы заключаются в следующем.
1. На основе анализа способов формального описания схем соединений, используемых в качестве исходных данных для задачи компоновки, а также анализа собственно методов решения этой задачи была обоснована необходимость разработки новых моделей и способов компоновки, а также их программной реализации.
2. Разработаны три способа оптимизации формальных описанний исходной схемы соединений: путем минимизации числа ребер графа, путем увеличения диаметра графа и путем уменьшения степеней вершин. Определение точной, простейшей структуры графа схемы уже на этапе компоновки ТС АСУ в значительной степени повышает скорость работы алгоритмов, обрабатывающих такие модели, и качество получаемого результата.
3. Разработан последовательно-параллельный алгоритм компоновки ТС АСУ, в основе которого лежит параметр отдаленности, дающий объективную характеристику степени близости элементов в схеме. Данный алгоритм позволяет получать качественные результаты как в случаях с сильно связанными группами элементов в исходной схеме соединений, так и в схемах с минимальным среднеквадратичным разбросом степеней вершин и с большим диаметром.
4. Алгоритмы и модели, полученные в результате работы, были использованы при создании программного комплекса разработки принципиальных схем FreeStyle Schematic, которая проходит опытную эксплуатацию в ОАО «Техприбор», ФГУП ЦНИИ «Морфизприбор» и ОАО «Авангард».
