锻压技术

PCB多工作板尺寸单一下料精确算法

英文标题：Exact algorithm of single cutting for PCB multi-working plate size

作者：王睿崔轶平崔耀东王婷婷

单位：广西大学华南理工大学

分类号：TP391

出版年,卷(期):页码：2019,44(3):17-23

摘要：

为解决PCB生产设备尺寸的限制问题，提出PCB多工作板尺寸单一下料精确算法。首先采用动态规划算法确定各种工作板尺寸及其所含PCB单元板数，然后采用拼合算法通过隐式枚举的方式生成所含工作板种数不超过一定数值的板材下料方案。控制板材下料方案中的工作板种数有利于简化切割工艺；通过隐式枚举法考察所有拼合情况，可以获取当前限制条件下的下料方案最优解。将本文下料算法分别与文献中的对比算法以及现有下料软件进行比较，实验计算结果表明，本文算法可以在简化切割工艺的同时保证板材利用率。

In order to solve the problem of size limitation of PCB production equipment, an exact algorithm of single cutting for PCB multi-working plate size was proposed. Firstly, the sizes of working plates and the number of PCB units were determined by the dynamic programming algorithm. Then, the cutting scheme of sheet metal with no more than a certain number of working plates was generated by the joining algorithm through implicit enumeration. Furthermore, controlling the number of working plates in the cutting scheme was beneficial to simplify the cutting process, and the optimal solution of cutting scheme under the current restrictive conditions could be obtained by investigating all the splicing conditions by implicit enumeration method. Compared the algorithm with the algorithm in the literature and the existing cutting software respectively，the experimental results show that the algorithm can simplify the cutting process and ensure the utilization ratio of working plate.

基金项目：

国家自然科学基金资助项目(71371058，61363026)

王睿（1993-），女，硕士研究生，E-mail：wr_0530@163.com；通讯作者：崔耀东（1957-），男，博士，教授，E-mail：ydcui@263.net

参考文献：

［1］Dyckhoff H. A typology of cutting and packing problems
［J］. European Journal of Operational Research, 1990, 44(2):145-159.

［2］扈少华, 潘立武. 矩形件五级剪切排样方式的一种生成算法
［J］. 锻压技术, 2018, 43(10):190-194.

Hu S H, Pan L W. A generating algorithm for five-level cutting layout pattern of rectangular part
［J］. Forging & Stamping Technology, 2018, 43(10):190-194.

［3］崔耀东, 张春玲, 赵谊. 同尺寸矩形毛坯排样的连分数分支定界算法
［J］. 计算机辅助设计与图形学学报, 2004, 16(2):252 -256.

Cui Y D, Zhang C L, Zhao Y. A continued fractions and branch-and-bound algorithm for generating cutting patterns with equal rectangles
［J］. Journal of Computer-Aided Design & Computer Graphics, 2004, 16 (2):252-256.

［4］李海生. 递归算法在单一矩形毛坯无约束最优排样中的应用
［J］. 重庆理工大学学报：自然科学版, 2017, 31(9):125-131.

Li H S. Recursive algorithm applied study on a single rectangle blanks unconstrained optimal layout
［J］. Journal of Chongqing Institute of Technology：Natural Science Edition, 2017, 31(9):125-131.

［5］孙英, 崔耀东. 简化同尺寸矩形毛坯排样方式的动态规划算法
［J］. 计算机应用与软件, 2008, 25(12):91-92.

Sun Y, Cui Y D. A dynamic programming algorithm for simplifying the cutting patterns of equal rectangular blanks
［J］. Computer Applications and Software, 2008, 25(12):91-92.

［6］姜永亮. 基于同质段矩形优化排样问题求解
［J］. 锻压技术, 2017, 42(5):159-163.

Jiang Y L. Solution on rectangular optimal layout based on the homogeneous segments
［J］. Forging & Stamping Technology, 2017, 42(5):159-163.

［7］杨少杰, 崔耀东. 同尺寸矩形毛坯排样算法
［J］. 桂林理工大学学报, 2013, 35(4):628-630.

Yang S J, Cui Y D. Algorithm for generating cutting patterns of equal rectangular items
［J］. Journal of Guilin University of Technology, 2013, 35(4):628-630.

［8］易向阳, 潘卫平, 张俊晖. 基于五块模式的单一矩形件排样算法
［J］. 图学学报, 2015, 36(4):521-525.

Yi X Y, Pan W P, Zhang J H. Algorithm for generating five block mode cutting patterns of single rectangular items
［J］. Journal of Graphics, 2015, 36(4):521-525.

［9］郭俐, 崔耀东. 有约束单一尺寸矩形毛坯最优排样的拼合算法
［J］. 农业机械学报, 2007, 38(10):140-144.

Guo L, Cui Y D. Joining method for generating constrained cutting patterns for rectangles of a single size
［J］. Transactions of the Chinese Society for Agricultural Machinery, 2007, 38(10):140-144.

［10］Agrawal P K. Minimizing trim loss in cutting rectangular blanks of a single size from a rectangular sheet using orthogonal guillotine cuts
［J］. European Journal of Operational Research, 1993, 64(3):410-422.

［11］李东兴. 同尺寸集成电路板下料算法研究
［D］. 南宁:广西大学, 2016.

Li D X. Research on the Algorithm for PCB Cutting Stock Problem Of Equal Rectangular Blanks
［D］. Nanning：Guangxi University, 2016.

服务与反馈：

【文章下载】【加入收藏】