Modification of Steinberg's Algorithm for Printed Circuit Board Topology Optimization and Production Process Reconfiguration


Аuthors

Liin E. A.1*, Nazarov A. V.1**, Smirnov K. K.2***

1. Moscow Aviation Institute (National Research University), 4, Volokolamskoe shosse, Moscow, А-80, GSP-3, 125993, Russia
2. Scientific Research Institute of System Analysis, 36/1, Nakhimovsky av., Moscow, 117218, Russia

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

Abstract

Modern printed circuit board (PCB) computer-aided design (CAD) systems, with rare exceptions, do not contain automatic component placement procedures. However, even if such tools are present within CAD software, they are used for optimizing an initial placement obtained either by interactive methods or by quasi-optimal placement algorithms. At the next stage of placement optimization, the classical Steinberg algorithm can be used, which guarantees an improvement in the quality of any predefined placement. Known implementations of the Steinberg algorithm perform element permutations only within the positions occupied by them. However, the algorithm's efficiency can be substantially increased by utilizing previously unused resources: a) in component placement — these are previously unoccupied but available areas of the PCB; b) in PCB production — this provides the process engineer with the opportunity to configure equipment at an early stage, minimizing its load and maximizing the probability of completing the shift-daily production task, which is especially critical in the design of radioelectronic equipment for aviation and rocket-space technology without external consulting support. The mathematical framework and results of experimental verification of the proposed modification are presented.

Keywords:

computer-aided design (CAD) system; automatic component placement on printed circuit boards; Monte Carlo method; minimization of total interconnect length; NP-complete problem; production process optimization; aviation and rocket-space technology

References

  1. Metropolis N., Rosenbluth A.W., Rosenbluth M.N., et al. (1953). Equation of State Calculations by Fast Computing Machines // The Journal of Chemical Physics. — Vol. 21. — Pp. 1087–1092. http://dx.doi.org/10.1063/1.1699114.
  2. Krishnan R. Placement Sequence Optimization in PCB Assembly Using Neighborhood Search Heuristics and Simulated Annealing (Master's thesis). — State University of New York at Binghamton. ProQuest Dissertations & Theses, 2014. — 1562256.
  3. Bykovsky N.V., Nekrasov S.A. Optimization of Placement of Heterogeneous Components on a Switching Field of Complex Topology Based on a Combinatorial Analog of the Gauss–Seidel Method // Izvestiya Vysshikh Uchebnykh Zavedeniy. Severo-Kavkazskiy Region. Technical Sciences. — 2025. — No. 1(225). — Pp. 19–28. DOI: 10.17213/1560-3644-2025-1-19-28.
  4. Guseynov O.A., Fatullaev A.A. Design Considerations for Power Supply Units of Multicopters // Trudy MAI. — 2024. — No. 138.
  5. Korobkov M.A., Zaikin V.D. Mask-Based Compensation Method for Non-Uniform Radiation in Direct-Write Lithography Systems Using Liquid Crystal Arrays // Trudy MAI. — 2023. — No. 132.
  6. Kureychik V.V., Kureychik V.L. VLSI Fragment Placement Based on Fractal Aggregation // Izvestiya SFU. Engineering Sciences. — 2015. — Pp. 196–205.
  7. Morozov K.K., Odinokov V.G., Kureychik V.M. Automated Design of Radioelectronic Equipment Structures: Textbook for Universities. — Moscow: Radio i Svyaz, 1983. — 280 p.
  8. Fedorov I.A. Process of Creating an Automated System Using Decision Tables // Trudy MAI. — 2012. — No. 53. — P. 9.
  9. Theory and Methods of Automation in Computer System Design / Ed. by M. Breyer. — Moscow: Mir Publishers, 1977. — 283 p.
  10. Kuliev E.V., Kureychik V.V., Kursitys I.O. Decision-Making in VLSI Component Placement Based on Wolf Swarm Behavior Model // International Conference on Soft Computing and Measurements. — 2018. — Vol. 1. — Pp. 712–715.
  11. Masyukov I.I., Borzov D.B., Titov D.V., Sokolova Yu.V. Mathematical Model and Hardware-Oriented Algorithm for Planning Software Placement in Systems-on-Chip // Trudy MAI. — 2021. — No. 119. DOI: 10.34759/trd-2021-119-13.
  12. Selyutin V.A. Computer-Aided Design of Electronic Devices. — Moscow: Sovetskoe Radio, 1977. — 383 p.
  13. Vantsov S.V., Liin E.A., Khomutskaya O.V. Application of the Monte Carlo Method in Monitoring Parameters of Technological Processes // Current Issues in Scientific Research: Collection of Articles from the XIII International Scientific and Practical Conference. — Saratov: NGO "Digital Science". — 2023. — Pp. 32–35.
  14. Anisin D.A., Morozov I.V. Automation of Technological Process Design // Trudy MAI. — 2012. — No. 51. — P. 27.
  15. Anamova R.R., Ripetskii A.V. Issues of Automation in Design Engineering for Airborne Radar Systems // Trudy MAI. — 2013. — No. 70. — P. 19.
  16. Bushin S.A., Kureychik V.V. Placement of Nodes and Blocks in Radioelectronic and Computer Equipment Based on Bio-Inspired Methods // Software Products and Systems. — 2010. — No. 1. — Pp. 12–14.
  17. Solonin S.I. The Histogram Method (Electronic Textbook). — Yekaterinburg: Novouralsk Technological Institute, NRNU MEPhI, 2014. — 8 p.
  18. Zeya M.M., Khlopkov A.Yu., Zhuo Z. Fundamental Approaches to Monte Carlo Methods in Computational Aerodynamics // Trudy MAI. — 2011. — No. 42. — P. 3.
  19. Nazarov A.V., Smirnov K.K. Optimization of Drill Idle Travel Using a Modified Monte Carlo Method // REDS: Telecommunication Devices and Systems. — Moscow. — 2024. — Vol. 14. — No. 1. — Pp. 40–50.
  20. Nazarov A.V., Smirnov K.K., Maksimov A.Yu. Optimization of Component Placement in Printed Modules Based on Signal Integrity Criteria // Engineering and Information Systems Technologies. — 2022. — No. 3. — Pp. 53–64.
  21. Abas V.M. Approximate Methods for Optimal Placement of Elements in Electrical and Electronic Circuits // Izvestiya Vysshikh Uchebnykh Zavedeniy. Severo-Kavkazskiy Region. Technical Sciences. — 2021. — No. 2(210). — Pp. 18–26. DOI: 10.17213/1560-3644-2021-2-18-26.
  22. Semenova I.V. Boolean Algebra and Its Application in Building Mathematical Models: Textbook. — Samara: Samara University Press, 2023. — 100 p.: ill.
  23. Il'in V.N., Lepikhin A.N. Investigation of Methods for Constructing Sets of Equivalent Alternatives in the Design of Radioelectronic Devices for Aircraft // Trudy MAI. — 2013. — No. 71. — P. 35.
  24. Daydobrenko B.N., Malika A.S. Automation of Radioelectronic Equipment Design. — Moscow: Vysshaya Shkola, 1980. — Pp. 125–132.
  25. Liin E.A., Borisova E.V. Application of Queuing Theory Elements in Mathematical Modeling of Manufacturing Processes // Trudy MAI. — Moscow. — 2025. — No. 143 (45).
  26. Liin E.A., Korobkov M.A., Khomutskaya O.V., Vantsov S.V. Formalization of a Production Unit's Operation for Developing an Imitation Model of Shift-Daily Task Execution // Scientific and Technical Bulletin of the Volga Region. — 2023. — No. 5. — Pp. 212–215.
  27. Karpenko A.P. Modern Search Optimization Algorithms: Nature-Inspired Algorithms (Textbook). — Moscow: Bauman Moscow State Technical University Press, 2014. — 46 p.
  28. Lee K. Fundamentals of CAD/CAM/CAE Systems. — [n.d.].
  29. Wang M., Yang X., Sarrafzadeh M. Standard-Cell Placement Tool for Large Industry Circuits // Proceedings of ICCAD 2000. — 2000. — Pp. 260–263.
  30. Ginzburg B.D. Module Placement Algorithm on a Board // Experience Exchange in Radio Industry. — 1972. — No. 4. — Pp. 31–33.
  31. Vantsov S.V., Vasiliev F.V., Khomutskaya O.V., Korobkov M.A. Problems of Technological Process Management // Scientific Instrument Engineering. — 2022. — Vol. 32. — No. 4. — Pp. 124–137. DOI: 10.18358/np-32-4-i124137.

Download

mai.ru — informational site MAI

Copyright © 2000-2026 by MAI

 Вход