Введение 5
1 Постановка задачи размещения и методы решения 6
1.1 Математическое описание коммутационных схем 9
1.2 Алгоритмы размещения 19
1.2.1 Задача размещения как задача квадратичного назначения 19
1.2.2 Непрерывные модели конструкций 28
1.2.3 Алгоритмы конструкторского проектирования 33
1.2.4 Алгоритмы решения задачи размещения 39
1.3 Эффективность алгоритмов размещения 54
Выводы по главе 1 65
2 ГКС как основа оценки эффективности алгоритмов размещения 66
2.1 Выявление параметров генерации 66
2.2 Формирование исходных данных 70
2.3 Принцип уточнения 73
2.4 Алгоритм генерации 74
Выводы по главе 2 75
3 Программный комплекс генерации коммутационных схем 76
3.1 Модуль работы с файлами 77
3.2 Программная реализация алгоритма размещения 78
3.3 Модуль визуализации результата размещения 80
3.3.1 Графический интерфейс 82
3.3.2 Пункт меню: файл 83
3.3.3 Пункты меню: Цветовой режим и Легенда 84
3.3.4 Отступ от края 85
3.3.5 Внутренние отступы 85
3.3.6 Размер элементов 86
3.3.7 Отрисовка схемы КП. Оценка качества 87
3.4 Анализатор коммутационных схем 88
3.5 Генератор коммутационных схем 89
3.5.1 Структуры данных коммутационной схемы 91
3.5.2 Механизм формирования данных генерации 93
3.5.3 Механизм уточнения 96
3.5.4 Алгоритм генерации 98
3.5.5 Интерфейс 98
3.6 Тестирование 100
Вывод по главе 3 104
Заключение 106
Список используемых источников
Современные системы проектирования печатных плат не являются полностью автоматизированными. Участие человека в процессе изготовление макета печатной платы до сих пор обязательно. Задача размещения электронных компонентов на плоскости печатной платы является одной из основных задач в процессе проектирования электронного устройства.
Выбор алгоритма решения задачи размещения может существенно повлиять на качество изготовления печатной платы и работы устройства в целом. Для успешного выбора алгоритма необходима информация о эффективности его работы при проектировании коммутационных схем на заданной элементной базе. Перебор всех алгоритмов с целью поиска лучшего результата не всегда является возможным решением проблемы выбора алгоритма размещения, так как при конструировании схем с большим количеством элементов (1000 и более) алгоритм может выполнятся сутки, что существенно может отразится на сроках проектирования и, с учётом итерационности процесса проектирования, как следствие, на конкурентоспособности компании производящей печатные платы.
Актуальность. Актуальность диссертационной работы заключается в повышении степени автоматизации процесса размещения за счёт получения информации о качестве работы алгоритмов путём генерации данных для тестирования алгоритмов размещения.
Цель. разработка механизма создания коммутационных схем с заданной элементной базой для получения тестовых данных для оценки качества решения задачи размещения.
Задачи:
— Анализ и выявление параметров генерации;
— Создание алгоритма формирования исходных данных для генерации;
— Создание алгоритмов генерации;
— Создание программы-генератора.
Обоснование актуальности исследования было сформулировано на основе необходимости для инженера-конструктора иметь в своём распоряжении большое количество коммутационных схем при проектировании устройств заданного класса с целью обоснования выбора эффективного алгоритма конструирования, в частности, алгоритма размещения.
Разработаны механизмы формирования коммутационных схем на базе математического аппарата формирования данных для генерации, что потребовало введение новых параметров для описания характеристик коммутационных схем, которые позволяют однозначно охарактеризовать связи каждого элемента с каждым внутри коммутационной схемы.
Разработан математический аппарат процесса создания коммутационных схем: введен термин "факт связи", создан алгоритм формирования данных для генерации, создана модель структуры данных для алгоритма генерации, создан алгоритм генерации.
Реализована программа, предоставляющая пользователю возможность генерировать схемы, в которую входит: интерактивный интерфейс предоставляющий пользователю возможность задавать значения параметров генерации, гарантирующий корректность данных, математическое ядро формирования ограничений параметров генерации и генерации коммутационных схем для обеспечения работы генератора коммутационных схем были разработаны вспомогательные программные модули: модуль работы с файлами, анализатор коммутационных схем, последовательно-итерационный алгоритм размещения, модуль визуализации результата размещения.
Апробация разработанного генератора коммутационных схем показала правдоподобность идеи генерации коммутационных схем приближенных к реальным.
