автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Средства и методы компоновки технического обеспечения автоматизированных систем управления

Па правах рукописи

СУХАРЕВ Анлрей Валериевич

СРЕДСТВА И МЕТОДЫ КОМПОНОВКИ ТЕХНИЧЕСКОГО ОБЕСПЕЧЕНИЯ АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ

Специальность 05.13.06 Автоматизация и управление технологическими процессами и производствами (промышленность)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург -2003

Рабою выполнена в федеральном государственном унитарном мредприяши цсшралыюм научно-исследовательском институте «Морфи {прибор» (Ф1УП ЦНИИ «Морфизприбор»).

Научным руководи Iель:

доктор технических паук Лузин Сергей Юрьевич

Официальные оппоненты:

док юр технических наук, профессор Анкудинов Георгий Иванович кандида! технических наук, доцент Лячек Юлий Теодосович

Ведущая организация ФГУП НИИ «Вектор»

Защита состоится 20 января 2004 года в 16 часов на заседании диссертационного совета Д 212.244.01 в Северо-Западном государственном заочном техническом университете по адресу: 191186, г. Санкт-Петербург, ул. Миллионная, д.5.

С диссертацией можно ознакомиться в библиотеке Северо-Западного государственного заочного технического университета.

Автореферат разослан 19 декабря 2003 года.

Учёный секретарь

диссертационного совета Иванова И.В.

2004-4 24769

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

По уровню организации разработки, масштабам проск!ирования, производства и эксплуатации АСУ специального назначения являются одними из самых сложных технических систем, созданных человечеством. Общий срок разработки составляет 7-10 лет, а период эксплуатации достигает 20 и более лет. В разработке, изготовлении и эксплуатации участвуют десятки специализированных научно-исследовательских и промышленных предприятий.

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

1. Высокие требования к надежности, качеству и унификации, определяемые большим сроком эксплуатации.

2. Воздействие широкого спектра дестабилизирующих факторов, определяемых условиями функционирования в динамически изменяемой внешней среде.

3. Широкое применений отечественной и зарубежной элементной базы, не отвечающей требованиям современных стандартов по стойкости к внешним воздействиям.

4. Высокие функциональные и массогабаритные показатели.

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

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

Ускорить и удешевить ] ~ :ию

можно путем разработки

и

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

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

Актуальность работы подтверждается проведением НИР и ОКР в рамках программ:

- федеральная целевая программа «Российские верфи»;

- федеральная программа «Российская электроника»;

- межотрослевая программа «Координация деятельности в области

промышленной автоматизации и системостроения».

Цель работы и задачи исследования. Целью диссертационной работы является разработка методов и программных средств решения задачи компоновки ТС АСУ.

В соответствии с этим в работе ставились и решались следующие задачи;

- анализ методов компоновки ТС АСУ, формирование объективной оценки качества результата;

-разрабо1ка методов оптимизации формальных описаний схем соединений;

- нахождение качественного параметра, характеризующего степень связности элементов в схеме соединений;

- ра ¡работка эффективного метода компоновки ТС АСУ;

-создание программных средств автоматизированной компоновки

ТС АСУ

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

Научная повита диссертационной работы:

- ра¡работка моделей коммутационных схем, решающих проблему неопределенное! и соединений в пределах электрической цепи;

- определение качеовенною параметра, характеризующего степень связное I и >леменюв в пределах создаваемого узла;

- разработка эффективного алгоритма компоновки ТС АСУ.

Ирак I ичеекпя ценное!ь диссертационной работы заключается в со!д.иши меюдики автоматизированной компоновки ТС АСУ и ее реализации в виде программного продукта, написанного на языке С++

Внедрение. Результаты диссертационной рабены о пило программного продукта FreeSlyie Schematic используются для со¡дания схем электрических принципиальных в ОАО «Техприбор» и ФГУП ЦНИИ «Морфизприбор». Кроме того, программой пользуются ряд частых лиц. Результаты диссертационной работы используются в учебном процессе Северо-Западного государственного заочного технического упивережеш.

Апробация работы Основные положения диссер!анионной работ докладывались и обсуждались на 51-ой научно-технической конференции студентов и аспирантов ГУТ, г. Санкт-Петербург, 1997 г; 53-ой научно-технической конференции студентов и аспирантов ГУТ, г. Санкт-Петербург, 1999 г; 53-ой научно-технической конференции профессорско-преподавательского состава, научных сотрудников и аспирантов ГУТ, г. Санкт-Петербург, 2000 г; П-ой международной научно-технической конференции студентов, аспирантов и молодых специалистов стран СНГ, г. Санкт-Петербург, 2000г; Юбилейной научно-технической конференции «Связисты СПб ГУТ и телекоммуникации XXI века», г. Сапк1-Пе1ербур|, 2000г; Ш-ой международной научно-технической конференции сгудснюи, аспирантов и молодых специалистов стран СНГ, г. Одесса, 2001 г; 55-ой научно-технической конференции студентов, аспирантов и молодых специалистов ГУТ, г. Санкт-Петербург, 200] г.; IV-ой международной научно-практической конференции "Современные информационные и электронные технологии", Одесса, 2003г.; 1-ой научно-технической конференции молодых специалистов ФГУП ЦНИИ "Морфизприбор", Санкт-Петербург, 2003г.

Публикации. По материалам диссертации опубликовано 9 печатных работ, из них: монография, учебное пособие, одна статья в научно-техническом сборнике и тезисы шести докладов на научно-технических конференциях.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения и списка литературы, включающего 81 наименование. Основная часть работы изложена на 107 страницах машинописного текста, содержит 18 рисунков и 8 таблиц.

На защиту выносятся:

1. Три способа оптимизации формального описания исходной схемы соединений: путем минимизации числа ребер графа, путем увеличения диаметра графа и путем уменьшения среднеквадратичного разброса степеней вершин. Определение точной, простейшей структуры графа схемы еще до этапа компоновки ТС АСУ в значительной степени повышает скорость работы алгоритмов, обрабатывающих такие модели, и качество получаемого результата.

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

3. Последовательно-параллельный метод компоновки ТС АСУ, использующий информацию об отдаленности вершин и групп вершин. Данный метод позволяет получать качественные результаты как в случаях с сильно связанными ¡руинами элементов в исходной схеме соединений, |пк и в схемах с минимальным среднеквадратичным разбросом степеней иершин и с большим диаметром

СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава посвящена постановке задачи и формулировке основных проблем, возникающих в процессе компоновки ТС АСУ.

Компоновка - процесс распределения элементов в узлы с учетом установленных критериев и ограничений.

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

Адекватное представление многоконтактной цепи - дерево имеет в

П

— раз меньше ребер, чем полный граф, построенный на тех же вершинах.

л-2

Основная сложность - выбор одного из П покрывающих деревьев для каждого полного подграфа.

Из полученной модели схемы соединений определяется степень близости расположения элементов, что является главным приоритетом распределения их в узлы, то есть чем ближе согласно схеме соединений располагаются элементы, тем больше вероятность, что они будут помещены в один узел. Отсюда, вторая задача - выбор способа определения степени близости вершин на графе. Наиболее простой способ

- определение кратчайшего пути между вершинами. Найдя кратчайшие пути между парами вершин, можно построить матрицу расстояний ТУ. 'Эта матрица содержит информацию для компоновки элементов, не имеющих непосредственной связи. Однако матрица расстояний не несет ин-

формации в явном виде о степени связности фафа и его частей, о числе путей различной длины между вершинами.

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

Во второй главе описано современное состояние способов формального описания схем соединений, используемых в качестве исходных данных для задачи компоновки, а также собственно методов решения этой задачи.

При выборе способа описания схемы соединений графом необходимо учитывать допустимую степень идеализации модели для использования в конкретной задаче конструкторского проектирования.

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

1 Вершины цепи соединяются при помощи 0,5л?1) связей -ребер полного графа.

2. Все П вершин цепи соединяются при помощи П-1 связей - ребер графа, имеющего структуру дерева.

4. Представления цепей в виде графов Кенига.

При выборе той или иной модели описания схемы соединений нужно учитывать следующие показатели:

- сложность описания;

- точность описания (в пределах рассматриваемых свойств);

- степень использования для решения конкретных конструкторских

задач;

- сложность алгоритмов обработки моделей.

Общая задача распределения формулируется как нелинейная целочисленная задача математического программирования. В задачах такого рода необходимо найти неотрицательные значения переменных (Х\, (Хъ ..., ап, удовлетворяющих заданным ограничениям произвольного вида, например,

/\{ах, аъ ап)>О, /2(аь аъ ■■■, а„)>О, М<*и аъ а„)>0.

и обращающих н максимум (минимум) нелинейную функцию этих переменных'

аъ ..., a„)^>max{min)

Примениlejibiio к задаче компоновки в качестве переменных Cl\, (12, ..., С1„ выступаю! вес, приписанный каждому элементу и переменная, определяющая положения элемента в узле; в качестве ограничений -максимальная вмесшмость узла и максимальное число выводов на узле, а и качестве нелинейной функции F - минимизация числа межузловых соединений.

Известно несколько формальных процедур для решения такого рода задач.

Это процедуры, использующие построение и исследование разрезов графа схемы, и процедура, использующая метод ветвей и границ.

В алгоритмах распределения, основанных на математических методах, в основном используются метод ветвей и границ. Такие алгоритмы состоят из следующих этапов. Сначала определяется нижняя оценка разбиения графа на заданное число частей. Затем производится построение дерева решений и осуществляется поиск оптимального результата.

Все известные приближенные (аппроксимирующие) алгоритмы распределения можно отнести к одной из трех групп:

а) алгоритмы последовательного заполнения узлов,

б) последовательно - параллельные алгоритмы,

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

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

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

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

При использовании итерационных алгоритмов сначала граф разбивается на определенное число частей произвольным обраюм, например с помощью последовательных алгоришов. Затем по некоторым правилам производится перестановка вершин из одной част в дру1ую с целью минимизации числа внешних ребер.

Каждый из этих методов в отдельности не дает ошималыюю по ряду параметров решения соответствующей задачи распределения. 11ри выборе метода решения конкретной задачи следует, прежде пссю, учитывать недостатки и достоинства каждого из рассмотренных ал гори тмов.

В третьей главе предложены три способа формального описания схем соединений.

Среди различных вариантов описания коммутационных схем наибольшей общностью и наглядностью обладает описание схемы в виде графа. Такое представление широко используется при математической постановке различных оптимизационных задач конструирования и позволяет в целом ряде случаев найти адекватные задачи в теории фафов и воспользовался при разработке алтригмов решения задач конструирования известными математическими методами.

Для получения адекватных и простейших формальных описаний исходных схем соединений необходимо определять каждую цепь в виде дерева.

1 способ. Оптимизация исходной схемы соединений путем минимизации числа ребер графа.

ПустьX = {Хь Хъ Хп} - множество вершин графа схемы; (? = {£?1, С?2, ..., Сгт} - множество подмножеств X, соответствующих каждой цепи принципиальной электрической схемы.

Из множества конфигураций деревьев каждой из цепей необходимо выбрать те, которые в объединении дают граф с минимальным числом ребер.

1. Анализируя матрицу инцидентности можно еще до начала основной части алгоритма в значительной степени упростить поставленную задачу. Речь идет о следующих свойствах цепей (цепь -

от

совокупность ребер, например Gi = ):

к=п

а) если цепи С7,- и С] равны, одну из них можно исключить из дальнейшего рассмотрения, увеличив вес ребер оставшейся цепи.

б) если некоторая цепь Ст* может быть полностью реализована совокупностью цепей (?, ...С,, то есть

U G,=GX,

то ее так же можно исключить из дальнейшего рассмотрения, увеличив вес ребер соответствующих цепи Gx в цепях G, ...G¡.

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

|G,|<|G2|<...<|GJ.

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

4. Выбирается первая цепь G¡, входящая в комплекс и строится вспомогательная матрица инцидентности строки и столбцы, которой преде 1авленм соответственно элементами, входящими в состав цепи G, и цепями G„ Gk, ..., Gj, ..., Gm, имеющими в своем составе эти ¡чеменгы. Причем должно выполняйся условие | G, ОС7/|>2.

Мели дерево цепи G, может быть полностью реализовано деревьями цепей Gfc G¡, ..., Gm, то при критерии минимума числа ребер графа для цепи G, необходимо выбирать такие ребра, которые являются общими для двух цепей G, и Gj, тем самым мы одновременно будем определять и фиксировать и ребра для дерева цепи G, и часть ребер деревьев цепей Gj.

huí и дерево цепи G, не может быть полностью реализовано деревьями цепей Gk ••■Gm, то все вышеизложенное можно применить уже к отдельной цепи G, и конкретно для нее решить задачу нахождения минимального дерева.

I loe ie выбора деревьев для первой цепи комплекса, осущес! вляекя выбор деревьев для остальных цепей комплекса, а за тем и оаальпыч цепей в возрастания их мощности. При определении деревьев д 1Я остальных цепей, необходимо учитывать число уже

зафиксированные для них ребер на этапе оптимизации комплекса и сначала рассматривать максимально реализованные цепи.

Если в итоге остались цепи (т, имеющие менее 2-х общих вершин с образованным деревом, то в таких случаях нет необходимости рассматривать все возможные деревья для каждой из цепей, а достаточно произвольно выбрать по одному дереву для них.

1*

<к Л

2 способ. Оптимизация исходной схемы соединений путем

увеличения диаметра графа. Основная идея этого способа заключается в выборе минимально пересекающихся цепей максимальной мощности; линейном размещении элементов, связанных данной цепью, и фиксации связей только между соседними в элементами в линейке.

Пусть задана схема, состоящая из элементов X— {Х\, ..., Хп}, связанных между собой цепями (г = -(С?1, Съ ■•■, . Пусть GJ = {GlJ,G2J,■^■,G|y} - множество цепей, которым принадлежат

контакты элемента Х^ , X'] — {х\} }- множество

элементов, связанных с элементом XJ и Сj= {С\} -

семейство множеств цепей, соединяющих элементы из X*} с Х^ то есть

причем

Если для каких-либо С} элементов из множества ХУ^ выполняется условие

^с^ (/Дей;/*/;),

г

л

£ и при этом

Т |\в,\О\)=0Ш

*

то эти элементы целесообразно располагать вытянутыми в линию 1 так, чтобы обеспечивалась возможность реализации остальных

((31 \ Су ) связей каждого элемента. Для таких классов элементов можно

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

\

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

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

Поскольку при реализации связей некоторого элемента множеством связей других элементов последние оказываются "частично реализованными" и притом, возможно, не оптимально, то необходимо установить критерий для определения последовательности решения этой задачи. Очевидно, что сначала необходимо реализовать связи наиболее "критичных" элементов, т.е. таких, дня которых вероятность реализации связей некоторой группой случайным образом выбранных связей элементов минимальна.

Поскольку вероятность такой «случайной» реализации внешних связей некоторого элемента тем меньше, чем короче его внешние связи (чем меньше звеньев в цепях) и тем больше, чем меньше количество внешних связей, то для определения последовательности решения задачи следующей оценкой:

* 1

где I - длина ] -й цепи (количество элементов, связанных ] -й цепью);

к - количество внешних связей элемента х1;

Алгоритм.

1. Для каждого элемента схемы определяется коэффициент

2. Элементы упорядочиваются по убыванию параметра Эта последовательность определяет порядок реализации связей элементов.

3. Выбирается элемент X,• с максимальным значением и составляется матрица инцидентности подграфа, вершинами которого, являются элементы смежные с X/.

4. Информация из полученной матрицы, записывается в виде псевдобулевой функции, в которой номера элементов (а они выступают в ка-

чесгве идентификаторов некоторых псевдобулевых переменных), записанных в столбце, связаны операцией дизъюнкции, а все элементарные дизъюнкции, соответствующие столбцам таблицы, связаны операцией конь-юнкции:

р,=псЬо ; = 1 <?=1

5. Воспользовавшись известным соотношением алгебры лошки а /\(а V Ь) = а {а, Ь = О V1), можно упростить указанную псевдобулеву функцию и получить наименьшее число звеньев, которому будет соответствовать терм минимальной длины. При этом в матрице смежности синтезируемой модели схемы необходимо отметить наличие связей вершины, соответствующей элементу Х„ с вершинами, соответствующими элементам, номера которых вошли в терм минимальной длины.

6. Для оставшихся элементов повторяются пункты 3-5.

В четвертой главе предложен эффективный алгоритм решения задачи компоновки.

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

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

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

На основании этого положения предлагается следующая метрика определения расстояний на графе для решения задач компоновки

b,=t\dk,~dk\,

где blf - «отдаленность» вершины X: от вершины Х},

dkl и dkj - элементы матрицы расстояний (кратчайших путей) D.

Полученную матрицу назовем матрицей отдаленностей.

Нетрудно убеди 1ься, что малейшие изменения графа приводят к изменению всей матрицы В, т.е. элементы è являются в некотором смысле интегральными характеристиками близости вершин Х( и XJt учитывающими структуру графа и реагирующими на ее изменения.

Последовательно-параллельный алгоритм, построенный на основе этой характеристики, состоит из двух этапов:

- подготовительный: последовательное распределение в образуемые части "центров кристаллизации";

- основной: последовательно-параллельное распределение вершин в части.

Подготовительный этап.

1. Пусть t - число образующихся узлов Ts. Определим в матрице отдаленностей шаХ Ьу (/, y'el, и), то есть пару вершин X, и Xj, максимально удаленных друг от друга и поместим их в разные узлы Tsk, (к -шаг распределения, начальный шаг к— 1). Если существует несколько пар вершин с одинаковым значением btJ, то выбор делается произвольно.

2. Если к= t, то распределение закончено. В противном случае переходим к пункту 3.

к

3. Среди множества неназначенных вершин X \ U X находим вер-

У=1

шину хр, имеющую

max

где Ь}р (/si, к) - отдаленность вершины Хр от вершины, назначенной в узел Tsk, и разместим ее в новом узле Tsk (к=к+1). Переход в пункт 2.

г к . —

По завершении этого этапа каждый узел Ts (/el,/) содержит ровно по одной вершине графа G

Основной этап

1. Строится матрица mtj | размера bxt (b - число неназначен-ных вершин, t - число узлов):

к

Щ,= Е da (Xj<EX \IJ*/)-

x/eTj 1=1

mt] - суммарная отдаленность неназначенной вершины X от вершин, назначенных в узел Tsk.

2. Матрица

м нормируется таким образом, чтобы сумма ее элементов равнялась нулю:

I ь 1 Ч \ b q

mv=m*

о ,=i q J=i oq ,=i J=i

(Подобное нормирование уменьшает погрешность результата при использовании "жадных" алгоритмов.)

3. Назначаем в каждый узел Ts по одной вершине таким образом, чтобы минимизировать проигрыш от неназначения данной вершины в этот узел:

а) в каждой из строк помечаем min т'у (уе1, t)~,

б) если в каком-либо столбце I только один помеченный элемент tnd, то вершина Х1 назначается в узел 7]

в) если в столбце / более одного помеченного элемента, то в каждой из строк, содержащих помеченные элементы в столбце / находим

mm'm'y

В узел Т\ назначается вершина Xt, для которой jmin mV-minVz'J = max.

г) если в каком-либо столбце / нет помеченных элементов, то в узел Г/ назначается вершина Х1, для которой

jmin - min

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

Если все вершины распределены, то процедура заканчивается.

Иначе, переходим снова к п.1 и строим снова матрицу || с новыми

параметрами.

В пятой главе приведены результаты экспериментальных исследований разработанного подхода к решений задачи компоновки ТС АСУ и его программной реализации

Система FreeStyle Schematic предназначена для графического ввода принципиальных схем; создания библиотек символов элементов, на основе которых и строятся схемы и компоновки элементов схемы в узлы.

Помимо стандартных функций рисования и редактирования, предоставляемых большинством современных схемотехнических редакторов, предлагаемый редактор обладает следующими отличительными особенностями:

- автоматическое размещение и трассировка принципиальной электронной схемы на базе описания Netlist и PDIF-, SPICE-форматов;

- импорт/экспорт PDIF-, SPlCE-файлов;

- автоматическая генерация символов элементов принципиальных схем в стандартах ГОСТ и ANSI с автоматизированным занесением данных об образе "посадочного места" на печатной плате;

- документирование схемы (оформление схемы в документ, соответствующий ГОСТ): автоматический выбор формата листа, добавление рамки, штампа и его заполнение;

- под держка иерархии (создание подсхем элементов).

Поскольку в настоящее время отсутствуют программные средства компоновки ТС АСУ (современные системы автоматизации проектирования электронной аппаратуры также не содержат процедур компоновки), эффективность разработанного алгоритма оценивалась на основе сравнительного анализа с основными представителями различных классов алгоритмов. На ряде примеров были исследованы последовательные (алгоритм Кодреса, использующий понятия конъюнкции и дизъюнкции и алгоритм, основанный на использовании информации о степенях вершин); последовательно-параллельные (алгоритм выделения квазиминимальных массивов по матрице смежности и алгоритм, основанный на использовании матрицы отдаленностей) и

итерационные алгоритмы (алгоритм использующий числа связности и алгоритм групповых перестановок) алгоритмы.

Эксперименты наглядно продемонстрировали преимущества предложенного подхода.

В заключении сформулированы основные научные и практические результаты работы.

В приложении даются сведения, подтверждающие использование полученных результатов в народном хозяйстве страны.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. На основе анализа способов формального описания схем соединений, используемых в качестве исходных данных для задачи компоновки, а также собственно методов решения этой задачи обоснована необходимость разработки новых моделей и способов компоновки, а также их программной реализации.

2. Разработаны три способа оптимизации формального описания исходной схемы соединений: путем минимизации числа ребер графа, путем увеличения диаметра графа и путем уменьшения степеней вершин. Определение точной, простейшей структуры графа схемы уже на этапе компоновки ТС АСУ в значительной степени повышает скорость работы алгоритмов, обрабатывающих такие модели, и качество получаемого результата.

3. Предложена новая метрика для определения расстояний на графе и параметр, характеризующий степень близости вершин как связанных непосредственно, так и не связанных.

4. Разработан последовательно-параллельный алгоритм компоновки ТС АСУ, в основе которого лежит параметр отдаленности, дающий объективную характеристику степени близости элементов в схеме. Данный алгоритм позволяет получать качественные результаты как в случаях с сильно связанными группами элементов в исходной схеме соединений, так и в схемах с минимальным среднеквадратичным разбросом степеней вершин и с большим диаметром.

5. Алгоритмы и модели, полученные в результате рабош, реализованы в виде программною продукта и используются в составе сис1смы автоматизированного проектирования принципиальных схем FreeStyle Schematic.

По материалам диссертации опубликованы следующие работы:

1 Сухарев А. В. Моделирование процессов синтеза печатного злекгромонтажа РОС как сложных систем./ Сухарев А В., IJIejieci В И // СПб СПбГУТ им проф М.А.Понч-Бруевича. - 1999 -227 с.

2.Сухарев А. В. Сравнение систем трассировки печатных плат // Труды учебных заведений связи. СПб: СПбГУТ им. проф. М.А.Бонч-Бруевича. 1999. -№165. - С. 125-128.

3.Сухарев А. В. Проектирование коммутационных структур с использованием топологического трассировщика // Труды 2-й международной НТК студентов, аспирантов и молодых специалистов стран СНГ СПб. СПбГУТ им проф. М.А.Бонч-Бруевича. - 2000. - С. 340341.

4 Сухарев А В Улучшение результатов трассировки на основе метода адекватного преобразования логических функций //Груды юбилейной научной конференции связисты СПб ГУТ и телекоммуникации XXI в. СПб: СПбГУТ им. проф. М.А.Бонч-Бруевича. - 2000. - С. 113.

З.Сухарев А. В. Модели и процедуры оптимизации в автоматизации проектирования (Программный комплекс FreeStyle Router). / Сухарев А.

B., Золоюв О.И. //СПб.: СЗТУ. - 2001. - 165 с.

6.Сухарев А. В. Сравнительный анализ существующих алгоритмов компоновки // 55-я НТК студентов, аспирантов и молодых специалистов. / Тезисы докладов СПб :СП6ГУТ им проф. М.А.Бонч-Бруевича. - 2001. -

C. 78.

7.Сухарев А. В. Задача компоновки РЭС. Использование нетрадиционной метрики для определения расстояний на> графе // Ма1ериалы 54-ой научно-технической конференции студентов, аспирантов и молодых специалистов СПб: СПбГУТ им. проф. М.А.Бонч-Бруевича. - 2002. - С. 95.

З.Сухарев А. В. К решению задачи компоновки электронных устройств. / Сухарев А. В., Соколов В. F,. // Труды четвертой международной научно-практической конференции современные информационные и электронные технологии. Одесса. - 2003 г. - С. 200.

9.Сухарев А. В. Методология проектирования модулей 1 и 2-го уровней на основе печатного монтажа в конструкторском подразделении // Труды 1-ой научно-технической конференции молодых специалистов ФГУП ЦНИИ «Морфизприбор». СПб: ФГУП ЦНИИ «Морфизприбор». -2003. - С.57.

Подписано к псча1и 16 12 2003 Тираж 60 экч.'Ъкач № 600

Отпечатано в Центре малой полжрафии 191131. Санк!-11е1србур1. бульвар Красных юрь.

H--42Í

РНБ Русский фонд

2004-4 24769

Введение.

1. Анализ алгоритмов компоновки ТС АСУ.

1.1. Постановка задачи и критерии компоновки ТС АСУ.

Выводы.

2. Общая характеристика алгоритмов компоновки ТС АСУ.

Выводы.

3. Алгоритмы оптимизации исходных схем соединений элементов в ТС АСУ.

3.1. Алгоритм оптимизации исходной схемы соединений путем минимизации числа ребер получаемого графа.

3.2. Алгоритм оптимизации исходной схемы соединений путем увеличения диаметра получаемого графа.

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

Выводы.

4. Разбиение графа схемы соединений на части.

4.1. Определение степени близости расположения вершин на графе

4.2. Последовательно-параллельный алгоритм разбиения графа, использующий матрицу отдаленностей.

Выводы.

5. Результаты экспериментальных исследований и программная реализация разработанных алгоритмов.

5.1. Экспериментальная оценка качества алгоритма, использующего матрицу отдаленностей.

5.2. Программная реализация процедуры компоновки, редактор принципиальных схем FreeStyle Schematic

5.3. Пример компоновки элементов схемы в узлы (разрезание схемы) в редакторе FreeStyle Schematic.

Выводы.

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

По уровню организации разработки, масштабам проектирования, производства и эксплуатации АСУ специального назначения являются одними из самых сложных технических систем, созданных человечеством. Общий срок разработки составляет 7-10 лет, а период эксплуатации достигает 20 и более лет. В разработке, изготовлении и эксплуатации участвуют десятки специализированных научно-исследовательских и промышленных предприятий.

Технические средства современных АСУ специального назначения характеризуются рядом особенностей, существенно влияющих на организацию процессов их разработки. К ним относятся:

1. Высокие требования к надежности, качеству и унификации, определяемые большим сроком эксплуатации.

2. Воздействие широкого спектра дестабилизирующих факторов, определяемых условиями функционирования в динамически изменяемой внешней среде.

3. Широкое применений отечественной и зарубежной элементной базы, не отвечающей требованиям современных стандартов по стойкости к внешним воздействиям.

4. Высокие функциональные и массогабаритные показатели.

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

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

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

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

Актуальность работы подтверждается проведением НИР и ОКР в рамках программ:

- федеральная целевая программа «Российсике верфи»;

- федеральная программа «Российская электроника»;

- межотрослевая программа «Координация деятельности в области промышленной автоматизации и системостроения»;

- программа Госстандарта РФ «Базовые несущие конструкции, печатные платы, сборка и монтаж электронных модулей».

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

В соответствии с этим в работе ставились и решались следующие задачи:

- анализ методов компоновки ТС АСУ, формирование объективной оценки качества результата;

-разработка методов оптимизации формальных описаний схем соединений;

-нахождение качественного параметра, характеризующего степень связности элементов в схеме соединений;

- разработка эффективного метода компоновки ТС АСУ;

-создание программных средств автоматизированной компоновки

ТС АСУ.

Научная новизна диссертационной работы заключается в:

- в разработке моделей коммутационных схем, решающих проблему неопределенности соединений в пределах электрической цепи;

- в определении качественного параметра, характеризующего степень связности элементов в пределах создаваемого узла;

- в разработке эффективного алгоритма компоновки ТС АСУ.

Практическая ценность диссертационной работы заключается в создании методики автоматизированной компоновки ТС АСУ и ее реализации в виде программного продукта, написанного на языке С++.

Результаты диссертационной работы в виде программного продукта FreeStyle Schematic используются в ОАО «Техприбор», ФГУП ЦНИИ «Морфизприбор» и ОАО «Авангард». Кроме того, программой пользуются ряд частных лиц. Результаты диссертационной работы используются в учебном процессе Северо-Западного государственного заочного технического университета.

Основные положения диссертационной работы докладывались и обсуждались на 51-ой научно-технической конференции студентов и аспирантов ГУТ, г. Санкт-Петербург, 1997 г; 53-ой научно-технической конференции студентов и аспирантов ГУТ, г. Санкт-Петербург, 1999 г; 53-ой научно-технической конференции профессорско-преподавательского состава, научных сотрудников и аспирантов ГУТ, г. Санкт-Петербург, 2000 г; 11-ой международной научно-технической конференции студентов, аспирантов и молодых специалистов стран СНГ, г. Санкт-Петербург, 2000г; Юбилейной научно-технической конференции «Связисты СПб ГУТ и телекоммуникации XXI века», г. Санкт-Петербург, 2000г; II 1-ой международной научно-технической конференции студентов, аспирантов и молодых специалистов стран СНГ, г. Одесса, 2001 г; 55-ой научно-технической конференции студентов, аспирантов и молодых специалистов ГУТ, г. Санкт-Петербург, 2001 г.; 1У-ой международной научно-практической конференции "Современные информационные и электронные технологии1', Одесса, 2003г.; 1-ой научно-технической конференции молодых специалистов ФГУП ЦНИИ "Морфизприбор", Санкт-Петербург, 2003 г.

По материалам диссертации опубликовано 9 печатных работ, из них 1 монография, 1 учебное пособие, 1 статья в научно-техническом сборнике и 6 тезисов докладов на научно-технических конференциях.

Диссертация состоит из введения, пяти глав, заключения и списка литературы, включающего 81 наименование. Основная часть работы изложена на 108 страницах машинописного текста, содержит 20 рисунков и 8 таблиц.

Выводы

1. На основании проведенных исследований можно утверждать, что разработанный последовательно-параллельный алгоритм компоновки ТС АСУ, в основе которого лежит параметр отдаленности, позволяет получать качественные результаты как в случаях с сильно связанными группами элементов в исходной схеме соединений, так и в схемах с минимальным среднеквадратичным разбросом степеней вершин и с большим диаметром.

2. Реализованная в редакторе принципиальных схем FreeStyle Schematic функция компоновки позволяет разбивать схемы на заданное число частей, минимизируя при этом число связей между образующимися узлами.

3. Имена цепей, соединяющих элементы, расположенные в различных узлах, задаются с помощью портов. Редактор автоматически именует такого рода цепи, при выполнении процесса компоновки.

101

Заключение

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

1. На основе анализа способов формального описания схем соединений, используемых в качестве исходных данных для задачи компоновки, а также анализа собственно методов решения этой задачи была обоснована необходимость разработки новых моделей и способов компоновки, а также их программной реализации.

2. Разработаны три способа оптимизации формальных описанний исходной схемы соединений: путем минимизации числа ребер графа, путем увеличения диаметра графа и путем уменьшения степеней вершин. Определение точной, простейшей структуры графа схемы уже на этапе компоновки ТС АСУ в значительной степени повышает скорость работы алгоритмов, обрабатывающих такие модели, и качество получаемого результата.

3. Разработан последовательно-параллельный алгоритм компоновки ТС АСУ, в основе которого лежит параметр отдаленности, дающий объективную характеристику степени близости элементов в схеме. Данный алгоритм позволяет получать качественные результаты как в случаях с сильно связанными группами элементов в исходной схеме соединений, так и в схемах с минимальным среднеквадратичным разбросом степеней вершин и с большим диаметром.

4. Алгоритмы и модели, полученные в результате работы, были использованы при создании программного комплекса разработки принципиальных схем FreeStyle Schematic, которая проходит опытную эксплуатацию в ОАО «Техприбор», ФГУП ЦНИИ «Морфизприбор» и ОАО «Авангард».

102

1. Абакумов В.Г., Сербии С.А. Сравнительный анализ методов конструирования печатных плат. - Управляющие системы и машины. 1981, Вып.5. С. 43-47.

2. Абрайтис Л.Б. Лучевой алгоритм для проведения печатных соеди- • нений. Вопросы радиоэлектроники. Сер.ЭВТ, 1968. Вып.З. С.35-45.

3. Абрайтис Л. Б., Гирнюс А. П. Канальная трассировка с учетом контактов разъемов и меняющейся ширины канала. Управляющие системы и машины, 1983. №6. С. 24-27.

4. Абрайтис Л.Б., Шнейкаускас Р.И., Жилявичус В.А. Автоматизация проектирования ЭВМ. М.: Сов. радио, 1978, 272с.

5. Авдеев Е. В., Еремин А. Т. и др. Системы автоматизированного проектирования в радиоэлектронике: Справочник. М.: Радио и связь, 1986, с. 368.

6. Авенье Е.П. Обзор методов проектирования топологии. ТИИЭР, 1983. т.71. № 1. с.60-70.

7. Автоматизация проектирования цифровых устройств./ Под ред. С.С.Бадулина. М.: Радио и связь, 1981. - 240с.

8. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного метода конструирования электронных устройств. Львов.: Вища школа, 1981.- 168с.

9. Балтрушайтис Р.И. Задача и оценки размещения. В сб.: Вычислительная техника. Каунас, КПИ, 1982, с.65-66.

10. Ю.Баранов С.И., Майоров С.А. Сахаров Э.П., Селютин В.А. Автоматизация проектирования цифровых устройств. Л.: Судостроение, 1979. -264с.

11. Бахтин Б.И. Автоматизация в проектировании и производстве печатных плат радиоэлектронной аппаратуры. Л.: Энергия, 1979. - 120с.

12. Бершадский A.M. Применение графов и гиперграфов для автоматизации проектирования РЭА и ЭВА. Изд-во Саратовского ун-та, 1983. -120с.

13. Берштейн JI.C., Сапрыкин A.A. Минимизация наиболее длинных связей при линейном размещении элементов схемы. Изв. АН СССР, Техн. кибернетика, 1981, № 6, с.91 -99.

14. Берштейн JI.C. Селянкин В.В. Линейное размещение гиперграфов. -Изв. АН СССР, Техн. кибернетика, 1973. № 3, с. 128 -135.

15. Бибило П.Н., Лицкевич В.Г. Покрытие булевой сети библиотечными элементами. Управляющие системы и машины, 1999, №6, с. 16-24.

16. Борде Б. И. Основы САПР неоднородных вычислительных устройств и систем: Учебное пособие. Красноярск: КГТУ. 2000. 350 с.

17. Борде Б. И. Программно-методический комплекс «Основы САПР неоднородных вычислительных устройств и систем». Красноярск: ГКТУ. 2000. CDROM.

18. Теория к методы автоматизации проектирования вычислительных систем // Под ред. Бреуера М. М.: Мир, 1977. - 284с.

19. Варшавский А.Д. Универсальный алгоритм размещения связных объектов в двухмерном пространстве. Экспресс-информация, ТС-9, Экономика и технология приборостроения, М.: 1979. Вып.5. - 16с.

20. Гаевенко А.Ю. Критерий качества и алгоритм размещения элементов РЭА. Тез. докл. Всесоюзного совещания "Автоматизация проектирования микроэлектронной аппаратуры", ч.2, 1Л., 1983, с.251-252.

21. Глушков В.М., Мясников В.А., Половинкин А.И. Автоматизация поискового конструирования. Вестник АН СССР, 1979, № 7. С.42-48.

22. Гндоян A.K. Об одном подходе к задаче трассировки. Вопросы радиоэлектроники, сер. ЭВТ, 1980, Вып. 14, С. 43-47.

23. Журавлев 10.Н. Теоретико-множественные методы в алгебре логики. В ст.: "Проблемы кибернетики", вып. 8, М., Физ.мат., 1962, с.5-44.

24. Гель П.П., Иванов-Есипович Н.К. Конструирование радиоэлектронной аппаратуры. Л.: Энергия, 1982, 232с.

25. Гндоян А.К. Об одном алгоритме покрытия внешних связей печатных плат. — Вопросы радиоэлектроники, сер. ЭВТ, 1979, Вып.9, С. 52-53.

26. Горбатов В.А., Демьянов В.Ф. Частотно-минимальный алгоритм покрытия булевых матриц. В сб.: Оптимизация дискретных систем управления., М.: ГВЦ Госплана СССР. 1972, с.48-57.

27. Горошенко А.Г. Матричный метод проектирования межсоединений на типовых печатных платах. УСиМ, 1975, № 5, с. 128-132.

28. Григоровский Л.Ф., Куранов Б.В. Ускоренный последовательный алгоритм размещения конструктивных элементов. Тез. докл. Всесоюзного совещания "Автоматизация проектирования микроэлектронной аппаратуры", ч.2, М., 1983, с.223-224.

29. Деньдобренко E.H., Малика A.C. Автоматизация проектирования радиоэлектронной аппаратуры. М.: Высшая школа, 1980. -384с.

30. Деньдобренко Б.Н., Селютин В.А. Опыт использования ЭВМ при конструировании радиоэлектронной аппаратуры. Л.: ЛДНТП, 1977. - 32с.

31. Ершов А. П. Введение в теоретическое программирование. М.: Наука. 1977.-288с.

32. Закревский Л.Д., Островский В.И. Оптимизация поиска кратчайшего покрытия. В сб.: Проблемы синтеза цифровых автоматов. - М.: Наука, 1968.- 150с.

33. Зуев Ю.А. Задача о покрытии: локальный подход и метод типа ветвей и границ. -Журн. выч. мат. и мат. физ., 1979. т. 19, № 6, с. 1533-1573.

34. Карапетян A.M. Автоматизация оптимального конструирования • ЭВМ. М.: Сов. радио, 1973.

35. Корячко В. П., Курейчик В. М., Норенков И. П. Теоретические основы САПР: Учебник для вузов. М.: Энергоатомиздат, 1987, с. 400, ил.

36. Кристофидес Н. Теория графов. М.: Мир, 1978. - 423с.

37. Кузьмин Б.А., Эйдес A.A. О критериях качества размещения. Управляющие системы и машины, №13, 1982, с.53-55.

38. Курейчик В. М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР: Учебник для вузов. М.: Радио и связь, 1990, с. 352, ил.

39. Лазарева Т.О., Крапчин Л. И., Покровский А. И. Алгоритм трассировки печатных соединении на основе представления о каналах. Автоматика и вычислительная техника, № 5, 1969, с. 12-15.

40. Литвинов З.Н. Об одном подходе к решению задачи минимизации . длины связывающей сети при размещении геометрических объектов. В сб.: . Размещение геометрических объектов и вопросы оптимального проектирования. ИК АН УССР, Киев, 1977. -48с.

41. Мелихов А. Н., Берштейи Л. С., Курейчик В. М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974, 304 с.

42. Морозов К.К. и др. Методы разбиения схем на конструктивно-законченные части. М.: Радио и связь, 1978. - 134с.

43. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование радиоэлектронной аппаратуры. М.: Радио и связь, 1983.-280с.

44. Морозов К.К. к др. Проектирование монтажных плат на ЭВМ. -М.: Советское радио, 1979. 224с.

45. Ненашев А. Н. Конструирование радиоэлектронных средств: Учебник для вузов. М.: Высшая школа, 1990, 432 с.

46. Норенков И.П., Маничев В.Б. Системы автоматизированного проектирования электронной и вычислительной аппаратуры. М.: Высшая школа, 1979.-272с.

47. Норенков И. П. Основы автоматизированного проектирования. Учебник для вузов. М.: Издано МГТУ им. Баумана. 2000. 360 с.

48. Островский В.М. К исследованию свойств кратчайших покрытий. -В сб.: Синтез дискретных автоматов и управляющих устройств. .

49. Парфенов Е. М., Камышная Э. Н. Усачов В. П. Проектирование конструкций радиоэлектронной аппаратуры: Учебное пособие для вузов. -М.: Радио и связь, 1989, с. 272.

50. Петренко А.И., Тетельбаум А.Я. Формальное конструирование . электронно-вычислительной аппаратуры. М.: Советское радио, 1979. - 253с.

51. Петренко А.П., Тетельбаум А.Я., Забалуев Н.Н. Топологические алгоритмы трассировки многослойных печатных плат. М.: Радио И связь, 1983.- 152с.

52. Петренко А.И. Основы автоматизации проектирования. Киев.: Техника, 1982.-295с.

53. Рощин В.А., Сергиенко И.В. Об одном подходе к решению задачи о покрытии. Кибернетика, 1984, № 6. с.65-69.

54. Рузаев Е.Н., Канунов А.И., Муравьев C.B. Алгоритмы нахождения минимального покрытия булевой матрицы. Изв. ВУЗов, Радиоэлектроника, 1981, №8. с.92-94.

55. Селютин В.А. Машинное конструирование электронных устройств. -М.: Советское радио, 1977, 384с.

56. Селютин В.А. Автоматизированное проектирование БИС. М.: Радио и связь, 1982. - 113с.

57. Сергиенко И.В., Рощин В.А. Один метод решения задачи о покрытии. ДАН УССР , 1983, №9, сер.А, с.73-75.

58. Смолич Г.Г., Смолич Л.И. Минимизация числа переходных отверстий при проектировании двухсторонних печатных плат. Обмен опытом в радиопромышленности, 1984, вып.11. с.54-56.

59. Соколов В.А., Фридман М.Г., Шеин П.,Д. Состояние и перспективы развития систем автоматизированного проектирования двухсторонних печатных плат. Изв.АН СССР, Техническая кибернетика, 1982, №2, с.171-178.

60. Соукуп И. Компоновка электронных схем. ТИИЭР, 1981. г.69, с.119-145.

61. Сухарев А. В. Моделирование процессов синтеза печатного электромонтажа РЭС как сложных систем./ Сухарев А. В., Шелест В.И. // СПб.:СПбГУТ им. проф. М.А.Бонч-Бруевича. 1999. -227 с.

62. Сухарев А. В. Модели и процедуры оптимизации в автоматизации проектирования (Программный комплекс FreeStyle Router). / Сухарев А. В., Золотое О.И. // СПб.: СЗТУ. 2001. - 165 с.

63. Толстун А.И., Мельничук И.Г., Горощенко А.Г. Программа направленной компоновки модулей. УСиМ. 1985, № 2, с. 29-33.

64. Финкелыитейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. -М.: Наука, 1973. 231с.

65. Фрумкин Г. Д. Расчет и конструирование радиоаппаратуры: Учебник для вузов. М.: Высшая школа, 1989, с. 463.

66. Харари Ф. Теория графов. М.: Мир, 1973. - 300с.

67. Шерип К.Ю. Синтез типоразмерных рядов базовых несущих конструкций радиоэлектронных средств АСУ.- СПб.: СПб.ГУТ им. проф. М.А. Бонч-Бруевича, 2000. 116 с.

68. Шрамченко Б. JI., Абакумов В. Г. Об определении матрицы смежности модулей. В кн.: Автоматизация проектирования и электронике. Вып.11., Киев.: Техника, 1975.

69. Штейн М. Е. Об ортогональных графах и оптимальных соединениях схем, Изв. АН СССР, Техн. Кибернетика, 1970, №2.

70. Юрин О.Н. Единая система автоматизации проектирования ЭВМ, проектирование блоков и узлов вычислительных машин, Киев, 1970.

71. Mailhot Г., De Micheli G. Algorithm for technology mapping based on binary decision diagrams and Boolean operations // IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems. 1993. - Vol.12, №5. - p. 599620.

72. Goodman E., Tetelbaum A., Kureichik V. A genetic algorithm approach to compaction, bin packing and nesting. Problems, Technical report №940702, Michigan state university, USA, 1994, p. 71.

73. Dergatchev S., Kureichik V. Allocation problem using genetic algorithm. SREU, Taganrog, №2, 1998, p. 251-253.

74. ACCEL EDA. Version 14. ACCEL PC AD PCB, ACCEL Tango PCB. User's Guide and Reference. ACCEL Technologies, Inc., 1999.

75. ACCEL EDA. Version 14. ACCEL PRO Route. User's Guide and Reference. ACCEL Technologies, Inc., 1999.

76. SPECCTRA. Version 5.3. Tutorial. Cooper & Chyan Technology, Inc.,1994.

77. SPECCTRA. Version 5.3. User's Reference. Cooper & Chyan Technology, Inc., 1994.1. АКТоб использовании результатов диссертационной работы Сухарева А. В.

78. Комиссия в составе Исправникова. В. А., Дорогунцева В. Г. и

79. Радушновой Е. М. составила настоящий акт о том, что теоретические и• практические результаты диссертационной работы Сухарева А. В., используются в научно-исследовательских и опытно-конструкторских работах предприятия ОАО «Техприбор».

80. Использование указанных математических моделей, алгоритмов и• программ обеспечивает многовариантный поиск наиболее целесообразных решений, существенно сокращает сроки и стоимость проектных работ.1. Нач. отдела АСУП1. Нач. отдела1. Вед. инженер-програг*

81. Исправников В. А./ /Дорогунцев В. Г./ /Радушнова Е. М./

82. УТВЕРЖДАЮ Проректор СЗТУ по учебной работе, д.т.н., проф.1. B.R Воронцов2003 г.1. АКТоб использовании диссертационной работы Сухарева A.B.в учебном процессе

83. Использование полученных соискателем теоретических и практических результатов снижает стоимость и сроки проектирования и производства новой техники, а также повышает ее конструктивные, технологические и эксплутационные характеристики.

84. Начальник отдела 1338, к.т.н.1. Тарасов Г.Г.

85. УТВЕРЖДАЮ Начальник 7 НИО,е^Л^НЬШ КОНСТруКТОр1. АКТоб использовании результатов диссертационной работы Сухарева А. В.

86. Использование указанных математических моделей, алгоритмов и программ обеспечивает многовариантный поиск наиболее целесообразных решений, существенно сокращает сроки и стоимость проектных работ.

87. Кульгин В. Л./ / Николаев Н. И./ /Федорова Н. А./