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


Авторы

Лийн Е. А.1*, Назаров А. В.1**, Смирнов К. К.2***

1. Московский авиационный институт (национальный исследовательский университет), 125993, г. Москва, Волоколамское шоссе, д. 4
2. Научно-исследовательский институт системных исследований Российской академии наук, Нахимовский проспект, 36, корп.1, Москва, 117218, Россия

*e-mail: elijn@bk.ru
**e-mail: rat-rut@yandex.ru
***e-mail: mail@konstantinsmirnov.com

Аннотация

Современные системы автоматизированного проектирования печатных плат, за редким исключением, не содержат автоматических процедур размещения элементов. Однако, даже если такие инструменты и присутствуют в составе программных средств САПР, они используются для оптимизации некоторого начального размещения, полученного либо интерактивными методами, либо алгоритмами квазиоптимального размещения. На следующем этапе оптимизации размещения может использоваться классический алгоритм Штейнберга, гарантированно повышающий качество любого наперёд заданного размещения. Известные реализации алгоритма Штейнберга выполняют перестановки элементов только в пределах занимаемых ими позиций. Однако можно существенно повысить эффективность алгоритма за счёт использования ранее не задействованных ресурсов: а) при размещении элементов — это ранее не занятые, но доступные для размещения участки платы; б) при производстве плат — возможность для технолога уже на ранней стадии конфигурировать оборудование, минимизируя его загрузку и максимизируя вероятность выполнения сменно-суточного задания, что особенно критично в условиях проектирования радиоэлектронных средств авиационной и ракетно-космической техники без внешней консалтинговой поддержки. Приводится математический аппарат и результаты экспериментальной проверки предложенной модификации.

Ключевые слова:

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

Список источников

  1. Метрополис Н., Розенблут А.В., Розенблут М.Н. и др. (1953), Уравнение вычислений состояния быстрыми вычислительными машинами. Журнал химической физики, — 21, — С. 1087–1092. http://dx.doi.org/10.1063/1.1699114.
  2. Krishnan, Rithul, Placement sequence optimization in pcb assembly using neighborhood search heuristics and simulated annealing — State University of New York at Binghamton ProQuest Dissertations & Theses, — 2014. — 1562256.
  3. Н.В. Быковский, С.А. Некрасов, Оптимизация размещения разногабаритных элементов на коммутационном поле сложной топологии на основе комбинаторного аналога метода Гаусса-Зейделя // Известия высших учебных заведений. Северо-Кавказский регион. Технические науки. — 2025. — № 1(225). — С. 19–28. — DOI 10.17213/1560-3644-2025-1-19-28.
  4. Гусейнов О.А. Вопросы проектирования узлов электропитания мультикоптеров / О.А. Гусейнов, А.А. Фатуллаев // Труды МАИ. — 2024. — № 138.
  5. Коробков М.А. Метод масочной компенсации неравномерности излучения в системе прямого экспонирования на основе жидкокристаллической матрицы / М.А. Коробков, В.Д. Зайкин // Труды МАИ. — 2023. — № 132.
  6. Курейчик В.В., Курейчик В.Л. Размещение фрагментов СБИС на основе фрактальной агрегации // Известия СФУ. Технические науки, 2015, — С. 196–205.
  7. К.К. Морозов, В.Г. Одиноков, В.М. Курейчик, Автоматизированное проектирование конструкций радиоэлектронной аппаратуры: Учебное пособие для вузов // Научно-техническое издательство "Радио и связь", 1983. — 280 с.
  8. Федоров, И.А. Процесс создания автоматизированной системы с использованием аппарата таблиц решений // Труды МАИ. — 2012. — № 53. — С. 9.
  9. Теория и методы автоматизации проектирования вычислительных систем // Под. ред. М. Брейера. — М.: Мир, 1977. — 283 с.
  10. Кулиев Э.В., Курейчик В.В., Курситыс И.О. Принятие решений в задаче размещения компонентов СБИС на основе модели поведения стаи волков // Международная конференция по мягким вычислениям и измерениям. — 018. — Т. 1. — С. 712–715.
  11. И.И. Масюков, Д.Б. Борзов, Д.В. Титов, Ю.В. Соколова, Математическая модель и аппаратно-ориентированный алгоритм планирования размещения программ в системах на кристалле // Труды МАИ. — 2021. — № 119. — DOI 10.34759/trd-2021-119-13.
  12. Селютин В.А. Машинное конструирование электронных устройств. — М: Сов. радио, 1977. — 383 с.
  13. Ванцов С.В., Лийн Е.А., Хомутская О.В., Использование метода Монте-Карло при контроле параметров технологических процессов // Актуальные вопросы научных исследований: сборник статей XIII Международной научно-практической конференции. — Саратов: НОП «Цифровая наука». — 2023. — С. 32–35.
  14. Д.А. Анисин, И.В. Морозов Автоматизация проектирования технологического процесса // Труды МАИ. — 2012. — № 51. — С. 27.
  15. Анамова Р.Р. Вопросы автоматизации конструкторских работ при проектировании комплексов авиационной радиолокации / Р.Р. Анамова, А.В. Рипецкий // Труды МАИ. — 2013. — № 70. — С. 19.
  16. Бушин С.А., Курейчик В.В. Размещения узлов и блоков радиоэлектронной и электронно-вычислительной техники на основе биохимических методов. — М: Программные продукты и системы, 2010, — № 1, — С. 12–14.
  17. Солонин С.И.; Метод гистограмм. Электронное учебное пособие. — Екатеринбург, Новоуральский технологический институт НИЯУ МИФИ, — 2014. — 8 с.
  18. Зея М.М. Основные подходы к построению методов Монте-Карло в вычислительной аэродинамике / М.М. Зея, А.Ю. Хлопков, З. Чжо // Труды МАИ. — 2011. — № 42. — С. 3.
  19. Назаров А.В., Смирнов К.К. Оптимизация холостого хода сверла модифицированным методом Монте-Карло. — M.: REDS: Телекоммуникационные устройства и системы. — 2024. — Т. 14. — № 1. — С. 40–50.
  20. Назаров А.В., Смирнов К.К., Максимов А.Ю. Оптимизация размещения элементов печатных модулей по критерию целостности сигналов // Технологии инженерных и информационных систем, — 2022. — № 3.  — С. 53–64
  21. Абас В.М., Приближенные методы оптимального размещения элементов электрических и электронных цепей // Известия высших учебных заведений. Северо-Кавказский регион. Технические науки. — 2021. — № 2(210). — С. 18–26. — DOI 10.17213/1560-3644-2021-2-18-26.
  22. Семенова И.В. Булева алгебра и ее применение при построении математических моделей: учебное пособие / Самара: Изд-во Самарского университета, 2023. — 100 с.: ил
  23. Ильин, В.Н. Исследование способов построения множеств равноценных альтернатив при проектировании радиоэлектронных устройств летательных аппаратов / В.Н. Ильин, А.Н. Лепехин // Труды МАИ. — 2013. — № 71. — С. 35.
  24. Деньдобренко Б.Н., Малика А. С Автоматизация конструирования РЭА.-М.: Высшая школа, 1980, — С.125–132
  25. Лийн Е.А., Борисова Е.В., Применение элементов системы массового обслуживания в задачах математического моделирования производственных процессов // Труды МАИ. — Москва. — 2025. — № 143 (45).
  26. Лийн Е.А., Коробков М.А., Хомутская О.В., Ванцов С.В., Формализация работы производственного участка для разработки имитационной модели выполнения сменно-суточного задания // Научно-технический вестник Поволжья. — 2023. — №5. — С. 212–215.
  27. Карпенко А.П.; Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: учебное пособие / А.П. Карпенко. — Москва: Издательство МГТУ им. Н. Э. Баумана, 2014. — 46 с.
  28. Ли К. Основы САПР (CAD, CAM, CAE). — 004.
  29. Wang M, Yang X, Sarrafzadeh M 2000 Standard-cell Placement Tool for Large Industry Circuits ICCAD2000. — С. 260–263.
  30. Гинзбург Б.Д. Алгоритм размещения модулей на плате // Обмен опытом в радиопромышленности. — 1972. — № 4. — С. 31–33.
  31. С.В. Ванцов, Ф.В. Васильев, О.В. Хомутская, М.А. Коробков, Задачи управления технологическими процессами // Научное приборостроение. — 2022. — Т. 32, — № 4. — С. 124-137. — DOI 10.18358/np-32-4-i124137.

Скачать статью

mai.ru — информационный портал Московского авиационного института

© МАИ, 2000—2026

 Вход