Research And Application Of Optimization Methods In PCB Layout

Nowadays, the demand for printed-circuit-board(PCB)is growing rapidly with the fast development of the hi-tech enterprises such as computer, electronic and communication industry. As a key technology to reduce the adjustment cost of production and improve the processing efficiency, PCB layout technology is becoming more and more valued by the PCB manufacters. This dissertation aims at solving the PCB layout optimization problem. The main research achievements are listed as follows.Firstly, the description of the concept of PCB layout optimization problem is discussed, followed by the analysis of the similarities and differences between the PCB layout optimization problem and the general two-dimensional rectangular packing problem. The mathematical model of the problem is build. The method and the framework of solution based on divide-and-conquer algorithm is discussed according to the characteristic of the problem..Secondly, algorithms in PCBs grouping problem are studied. A new solution called “sample- duplicate” is proposed according to the characteristic of the objective demand of the problem. A heuristic algorithm is implemented to divide all the PCBs into several groups and each group of PCBs can be nested by the proportion of the PCB number on each sample plate. Then the final sort of PCB panels can be reduced by duplicating those sample plates and t he validity of the algorithm is proved by a case test.Thirdly, algorithms in PCB layout problem with process constraints are studied. The process constraints of PC B layout problem are summarized and the corresponding mathematical model is established. According to the analysis of the mathematical model and the characteristic of the problem, an improved lowest-gravity-center principle based on NFP(No Fit Polygon) is proposed. The placement position and the shape(rotation and set) of each PCB can be obtained at the same time by calculating the NFPs of the different rotations and sets of each PC B, while the process constraints are satisfied. The algorithm based on calculating the fitness of the PCBs is also presented to optimize the packing order of the PC Bs and improve the probability of obtaining feasible solutions. At last, the validity of the algorithm is proved by a case test.Finally, the PCB layout system is developed based on the PCB layout optimization algorithm proposed above and the practical demand. According to the typical enterprise application, the PCB layout optimization algorithm can achieve better results than the traditional PCB layout methods and be a technical support for reducing the production costs and improving the production efficiency.