Transactions of Materials and Heat Treatment

Title：Dynamic programming algorithms of single cutting for PCB

Authors： Cui Yaodong Li Fengjie Chen Qiulian

Unit： Guangxi University

KeyWords： PCB problem of single cutting material utilization dynamic programming branch-and-bound

ClassificationCode：TP391

year,vol(issue):pagenumber：2019,44(9):23-26

Abstract：

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.

Funds：

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

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

Reference：

［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.

Service：

【This site has not yet opened Download Service】【Add Favorite】