Проектирование размещения геометрических объектов на многосвязном ортогональном полигоне

• Автор: Хасанова, Элина Ильдаровна
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Уфа
• Количество страниц: 187 с. : ил.

Оглавление

Использованные обозначения

Введение.
Глава 1. Задачи размещения объектов на плоских областях и примыкающие к ним проблемы покрытия модели и методы решения
1.1. Сферы применения алгоритма размещения прямоугольных предметов в многосвязиый ортогональный полигон

1.2. Модели и методы решения задач плотного размещения предметов

1.3. Модели и методы решения задач размещения в область с препятствиями

двухсвязные полигоны

1.4. Постановки задач покрытия

Выводы по главе 1.

Глава 2. Задачи и методы проектирования плотного размещения технических объектов на многосвязных полигонах
2.1. Основная задача проектирования плотного размещения технических объектов на многосвязных полигонах
2.2. Уровневый метод проектирования гильотинного сквозного размещения предметов на многосвязных полигонах.
2.3. Задача разделения многосвязного полигона на прямоугольные участки и методы ее решения.
2.4. Проектирование плотного размещения технических объектов на многосвязном полигоне.
Выводы по главе 2.
Глава 3. Подсистема автоматизации проектирования инвариантных размещений объектов на многосвязном полигоне.
3.1. Структура системы проектирования размещения геометрических объектов на многосвязном ортогональном полигоне
3.2. Подсистема проектирования плана размещения
Выводы по главе 3
Глава 4. Численные эксперименты
4.1. Численные эксперименты на безотходных примерах
4.2. Сравнительный анализ работы алгоритма размещения геометрических объектов в многосвязный ортогональный полигон и метода холодного отжига.
4.3. Планирование складского помещения ООО Матрицатрейд с использованием метода размещения геометрических объектов в многосвязный ортогональный полигон.
Выводы по главе 4
Заключение.
Литература


Рассматривается задача размещения прямоугольных объектов сквозными гильотинными рядами на многосвязном ортогональном полигоне (МОП). Под миогосвязиым полигоном понимается ортогональный многоугольник, внутри которого расположены односвязные многоугольники. В том или ином виде человек достаточно часто сталкивается с этой на практике. В зависимости от сферы деятельности в рамках се постановки могут возникать дополнительные условия и ограничения. В главе рассматриваются следующие области: проектирование сверхбольших интегральных схем, проектирование размещения товаров в складских помещениях, размещение грузов на палубах судов, раскрой промышленных материалов (стекло, дерево). Проектирование размещения объектов на многосвязных областях может быть сведено к решению ряда задач размещения на прямоугольных областях и их покрытию. В главе приведен обзор задач плотного размещения предметов внутри прямоугольной области и задач покрытия плоских областей. Рассмотрены модели и методы решения задач раскроя и упаковки, которые близки к проблемам плотного размещения. Приведен обзор задач покрытия областей различной формы и алгоритмов их решения. Задача размещения прямоугольных объектов на многосвязных полигонах не является случайной. В том или ином виде человек достаточно часто сталкивается с ней на практике. В зависимости от сферы деятельности в рамках ее постановки могут возникать дополнительные условия и ограничения. Модуль постпроцессор-ной обработки информации представлен на рис. Рассматриваются следующие области использования предложенных алгоритмов: проектирование сверхбольших интегральных схем, проектирование размещения товаров в складских помещениях, размещение грузов на палубах судов, раскрой промышленных материалов (стекло, дерево). Рисунок 1. Основу элементной базы современных радиоэлектронных устройств составляют большие интегральные схемы - БИС (до элементов в кристалле) и сверхбольшие интегральные схемы - СБИС (до 1 млн. Возрастание степени интеграции и сложности СБИС из-за непрерывного совершенствования технологий заставляет разрабатывать новые методики и средства проектирования СБИС. Проблемы проектирования СБИС трудно формализуемы и многие авторы представляют пользователю несколько альтернативных схем. Такой подход позволяет использовать методы комбинаторной оптимизации на отдельных этапах проектирования при решении различных подзадач. Общий цикл проектирования СБИС []. Производство БИС и СБИС разбивается на три этапа: проектирование, изготовление, тестирование. Проектирование СБИС - это сложный и длительный процесс. Разработка СБИС должна осуществляться в кратчайшие сроки, с наименьшими затратами. Одним из путей достижения этой цели является автоматизация процесса проектирования. Она охватывает исследования, разработку, производство и эксплуатацию технических, математических, программных, информационных, организационных, методических средств и управление жизненным циклом продукции. При проектировании СБИС выполняется следующая последовательность этапов (шагов) [9, , 7, ]: системная спецификация; функциональное проектирование; логическое проектирование; схемное проектирование; конструкторское проектирование; технологическое проектирование; сборка, изготовление корпусов, тестирование и контроль. Конструкторское проектирование СБИС. Входной информацией для конструкторского проектирования служат функциональные схемы, а выходом — топология схемы. Основными этапами являются покрытие, разбиение, планирование, размещение, трассировка, сжатие (компакция), экстракция и верификация []. Покрытие. В результате покрытия функциональной схемы элементами заданного набора получается электрическая принципиальная схема, функционально эквивалентная исходной []. Разбиение. В связи с ограниченными возможностями вычислительных средств выполняется разбиение схемы на части и группирование компонентов в блоки. С этой целью может быть использован матричный метод, предложенный в настоящей работе [3, ]. Планирование и размещение - размещение на поле кристалла блоков, полученных на этапе разбиения, имеющих заданную площадь и не имеющих фиксированных размеров [9].