Transactions of Materials and Heat Treatment

Title：Exact algorithm of single cutting for PCB multi-working plate size

Authors： Wang Rui Cui Yiping Cui Yaodong Wang Tingting

Unit： Guangxi University South China University of Technology

KeyWords： working plate PCB unit dynamic programming joining algorithm cutting process

ClassificationCode：TP391

year,vol(issue):pagenumber：2019,44(3):17-23

Abstract：

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.

Funds：

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

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

Reference：

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

Service：

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