锻压技术

集成电路板单一下料的动态规划算法

英文标题：Dynamic programming algorithms of single cutting for PCB

作者：崔耀东黎凤洁陈秋莲

单位：广西大学

分类号：TP391

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

摘要：

针对集成电路板单一下料问题，提出两种动态规划算法：基本算法和改进算法，采用分支定界技术加速问题求解。将集成电路板单一下料过程分为两个阶段：第1阶段将板材剪切成相同尺寸的矩形工作板，第2阶段将工作板切成矩形单元板。优化目标为单张板材中所布局的矩形单元板数最大。改进算法利用动态规划算法的全容量特性，通过排除无潜力工作板，大幅度地缩短计算时间。实验结果表明：改进算法保证了解的最优性，使材料利用率达到最大；同时，算法求解速度快，计算时间均在0.4 s以内，可以满足集成电路板制造业优化下料和网上订单系统的实时报价需要。

For the problem of single cutting for PCB, two dynamic programming algorithms, namely basic algorithm and improved algorithm, were presented by the branch-and-bound technique to speed up the solution process, and the process of single cutting for PCB was divided into two stages. In the first stage, the sheet was cut into the identical rectangular panels, and in the second stage, the panels were divided into rectangular units. However, the optimization objective was to maximize the number of rectangular units laid out in a single plate. Furthermore, the improved algorithm utilized the full-capacity characteristics of the dynamic programming algorithm, and the calculating time was greatly reduced by eliminating the panels without potential. The experimental results show that the optimality of the solution is guaranteed and the material utilization ratio is maximized by the improved algorithm.At the same time, the solving speed of the algorithm is fast within 0.4 s, which can meet the requirements of optimizing the cutting plans of the PCB manufacturing industry and the real-time quotation of the online order system.

基金项目：

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

崔耀东（1957-），男，博士，教授 E-mail：ydcui@263.net 通讯作者：陈秋莲（1974-），女，博士，副教授 E-mail：cql668@163.com

参考文献：

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

Li D X. Research on Unconstrained PCB Cutting Problem of a Single Size
［D］. Nanning：Guangxi University, 2016.

［2］吴电建，阎春平，李俊，等. 面向可加工性的矩形件优化下料方法
［J］. 计算机集成制造系统, 2018, 24 (6): 1374-1382.

Wu D J, Yan C P, Li J, et al. Manufacturability-oriented rectangular parts cutting stock method
［J］. Computer Integrated Manufacturing Systems, 2018, 24(6): 1374-1382.

［3］呼万哲，郑忠，龙建宇，等. 中厚板考虑母板和板坯规格不确定性的下料问题建模及求解
［J］. 计算机集成制造系统, 2017, 23 (11): 2508-2517.

Hu W Z, Zheng Z, Long J Y, et al. Modeling and solving cutting stock problem considering specification uncertainties of mother plate and slab of medium and heavy plate
［J］. Computer Integrated Manufacturing Systems, 2017, 23(11): 2508- 2517.

［4］张帆，刘强，张浩，等. 面向多规格板材的矩形工件排样优化方法
［J］. 计算机集成制造系统, 2015, 21 (11): 2921-2928.

Zhang F, Liu Q, Zhang H, et al. Packing optimization of rectangle workpieces oriented to variable-sized bin
［J］. Computer Integrated Manufacturing Systems, 2015, 21 (11): 2921-2928.

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

［6］Arslanov M Z. Continued fractions in optimal cutting of a rectangular sheet into equal small rectangles
［J］. European Journal of Operational Research, 2000, 125 (2): 239-248.

［7］Cui Y. Dynamic programming algorithms for the optimal cutting of equal rectangles
［J］. Applied Mathematical Modelling，2005, 29 (11): 1040-1053.

［8］Cui Y, Gu T, Hu W. A computational improvement to the dynamic programming algorithm for the optimal cutting of equal rectangles
［J］. International Journal of Information and Management Sciences, 2009, 20 (3): 453-458.

［9］何冬黎, 许道云, 崔耀东. 基于递归的同尺寸矩形最优剪切排样算法
［J］. 广西师范大学学报:自然科学版，2008，26(2)：102-105.

He D L, Xu D Y, Cui Y D. Recursive algorithm for optimal guillotine-cutting of equal rectangles
［J］. Journal of Guangxi Normal University: Natural Science Edition, 2008, 26(2):102-105.

［10］曾兆敏, 王祺, 潘立武. 冲压条带二维优化排样问题的一种启发式算法
［J］. 锻压技术, 2018, 43(7): 204-208.

Zeng Z M, Wang Q, Pang L W. A heuristic algorithm for two-dimensional optimal nesting problem of stamping strips
［J］. Forging & Stamping Technology, 2018, 43(7): 204-208.

［11］曹静静, 崔耀东, 李东兴. 多线材变截面一维下料问题解法研究
［J］. 锻压技术, 2017，42(1):161-165.

Cao J J, Cui Y D, Li D X. Study on the solution of one-dimensional cutting stock for multiple stock lengths with variable cross-section
［J］. Forging & Stamping Technology, 2017, 42(1): 161-165.

［12］杜远坤, 牛庆丽, 管卫利. 同尺寸矩形件多板材下料算法
［J］. 机械设计与制造，2017, (8): 61-64.

Du Y K, Niu Q L, Guan W L. An algorithm for the problem of cutting stock equal rectangular items with multiple plates
［J］. Machinery Design & Manufacture, 2017, (8): 61-64.

服务与反馈：

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