Placement of components on complex printed circuit boards using a modified Monte-Carlo method

Аuthors

Nazarov A. V.^*, Liin E. A.^**, Trung T. H.^***

Moscow Aviation Institute (National Research University), 4, Volokolamskoe shosse, Moscow, А-80, GSP-3, 125993, Russia

*e-mail: rat-rut@yandex.ru
**e-mail: elijn@bk.ru
***e-mail: tranhieu.hnue.99@gmail.com

Abstract

Despite the abundance of printed circuit board (PCB) computer-aided design (CAD) systems, none of them provides efficient tools for automatic component placement that meet the stringent requirements imposed on radioelectronic equipment used in aviation and rocket-space technology. In such applications, minimal mass and dimensions, high reliability, and strict limitations on total interconnect length are critical to ensure required electrical performance and electromagnetic compatibility. Typically, existing CAD systems address this problem using interactive placement methods. As a result, design time increases significantly, and the resulting placement remains far from even quasi-optimal. This situation stems from the factorial computational complexity of the placement problem and its high dimensionality (number of components (n > 100). The challenge is further exacerbated by the fact that evaluating the total interconnect length for each of the N placement variants requires approximately n2 multiplication operations, leading to an overall computational complexity of about (n2 × n!) / 2.
This paper proposes a modification of the classical Monte Carlo method that enables obtaining a quasi-optimal PCB component placement within acceptable computation time while satisfying the rigorous constraints typical of onboard avionics and spaceborne electronics. The key distinction of the proposed approach lies in establishing a direct link between the design phase and production implementation: minimizing the total interconnect length directly reduces assembly time, decreases the number of equipment setup changes, and increases the utilization rate of production resources. This allows quantitative assessment of manufacturing efficiency already at the design stage and enables selection of placement alternatives that maximize the probability of successfully completing shift-daily production assignments in the context of small-batch instrument manufacturing.
A comparative analysis of the proposed algorithm’s efficiency against well-known placement algorithms is carried out on specific, application-relevant examples. The results demonstrate that the modified Monte Carlo method reduces the total interconnect length by nearly a factor of 2.2 compared to the classical approach. The study also demonstrates the potential for integration into agent-based design systems, making it highly relevant for contemporary industrial and research challenges.

Keywords:

computer-aided design (CAD) system; automatic component placement on a printed circuit board; Monte Carlo method; minimization of total interconnect length; NP complete problem; production process optimization.

References

1. Il’in, V.N., & Lepikhin, A.N. (2013). Investigation of methods for constructing sets of equivalent alternatives in the design of radioelectronic devices for aircraft. Trudy MAI, 71, 35.
2. Anamova, R.R., & Ripetskii, A.V. (2013). Issues of automation in design engineering for airborne radar systems. Trudy MAI, 70, 19.
3. Guseinov, O.A., & Fatullaev, A.A. (2024). Design considerations for power supply units of multicopters. Trudy MAI, 138.
4. Ginzburg, B.D. (1972). Module placement algorithm on a board. Experience Exchange in Radio Industry, 4, 31–33.
5. Breyer, M. (Ed.). (1977). Theory and Methods of Automation in Computer System Design. Moscow: Mir Publishers. 283 p.
6. Lijn E.A., Borisova E.V. Application of queuing system elements in mathematical modeling of production processes // Trudy MAI. — Moscow. — 2025. — No. 143 (45).
7. Lijn, 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 // Nauchno-tekhnicheskiy vestnik Povolzh’ya. — 2023. — No. 5. — P. 212–215.
8. Sel’utin, V.A. (1977). Computer-Aided Design of Electronic Devices. Moscow: Sovetskoe Radio. 383 p.
9. Bushin, S.A., & Kureychik, V.V. (2010). Placement of nodes and blocks in radioelectronic and computer equipment based on bio-inspired methods. Programmnye Produkty i Sistemy, 1, 12–14.
10. Karpenko, A.P. (2014). Modern Search Optimization Algorithms: Nature-Inspired Algorithms (Textbook). Moscow: Bauman Moscow State Technical University Press. 46 p.
11. Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., & Teller, E. (1953). Equation of state calculations by fast computing machines. The Journal of Chemical Physics, 21, 1087–1092. https://doi.org/10.1063/1.1699114
12. Lee, K. (n.d.). Fundamentals of CAD/CAM/CAE Systems. — 004.
13. Hashiba, S., & Chang, T.C. (1992). Heuristic and simulated annealing approaches to PCB assembly setup reduction. In Proceedings of the Eighth International PROLAMAT Conference: Man in CIM (pp. 24–26), Tokyo, Japan. https://doi.org/10.1016/B978-0-444-89465-6.50070-3
14. Krishnan, R. (2014). 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, 1562256.
15. Korobkov, M.A., & Zaikin, V.D. (2023). Mask-based compensation method for non-uniform radiation in direct-write lithography systems using liquid crystal arrays. Trudy MAI, 132.
16. Nazarov, A.V., & Smirnov, K.K. (2024). Optimization of drill idle travel using a modified Monte Carlo method. REDS: Telecommunication Devices and Systems, 14(1), 40–50.
17. Zeya, M.M., Khlopkov, A. Yu., & Zhuo, Z. (2011). Fundamental approaches to Monte Carlo methods in computational aerodynamics. Trudy MAI, 42, 3.
18. Vantsov, S.V., Liin, E.A., & Khomutskaya, O.V. (2023). Application of the Monte Carlo method in monitoring parameters of technological processes. In Current Issues in Scientific Research: Collection of Articles from the XIII International Scientific and Practical Conference (pp. 32–35). Saratov: NGO “Digital Science”.
19. Solonin, S.I. (2014). The Histogram Method (Electronic textbook). Novouralsk Technological Institute, NRNU MEPhI. Yekaterinburg. 8 p.
20. Kuliev, E.V., Kureychik, V.V., & Kursitys, I.O. (2018). Decision-making in VLSI component placement based on wolf swarm behavior model. In Proceedings of the International Conference on Soft Computing and Measurements (Vol. 1, pp. 712–715).
21. Wang, M., Yang, X., & Sarrafzadeh, M. (2000). Standard-cell placement tool for large industry circuits. In Proceedings of ICCAD 2000 (pp. 260–263).
22. Kureychik, V.V., & Kureychik, V.L. (2015). VLSI fragment placement based on fractal aggregation. Izvestiya SFU. Engineering Sciences, 196–205.
23. Nazarov, A.V., Smirnov, K.K., & Maksimov, A. Yu. (2022). Optimization of component placement in printed modules based on signal integrity criteria. Engineering and Information Systems Technologies, 3, 53–64.

Download