Research On Unconstrained PCB Cutting Problem Of A Single Size

PCB(printed circuit board)is an important component of electric industry.Many PCB factories produce PCB units by a way that places as many as PCB together on a sheet,cuts after a series of molding process,so as to produce a lot of PCB units in one time.In the actual production process,many factories are willing to use panel producing pattern that cuts sheet into panels as the first step,then cuts panels into units.Based on this situation,we design a generating algorithm for PCB cutting problem considering panel model in order to guide industrial production.Unconstrained PCB cutting problem belongs to single rectangle placement problem,where there is no limit on the number of blanks and the direction is uncertain.A lot of mature single rectangle placement algorithms have been proposed and both calculation time and the layout result are satisfactory.However,the layout of the panel on the sheet of PCB cutting problem belongs to nested placement problem,the type of panel is not limited,but the size are constrained.Therefore,this kind of problem is more complicated than the single rectangle placement problem.The algorithm is divided into three steps.Step 1.Generate panel:stripes are composed of a set of blanks,multiple strips are combined to form the panel layout,use dynamic programming algorithm to generate the value and layout of all sizes of panel,record the better panel which value increases with the size increased.Step 2.Generate Segment:use backpack algorithm to combine the different size and direction of the panel to form a segment,ensure the maximum value of the segment fast,but do not record the layout of its way.Step 3.generate the sheet:use backpack algorithm again to combine all the segment to form the layout of sheet,considering both the X-segment an Y-segment layout,which has a higher utilization rate as the final solution.An exact algorithm is designed to solve such problem to assess the proposed(heuristic)algorithm.The test results show that the proposed algorithm has a little bit lower material utilization level than the exact algorithm,but the computation time is doubled decreased and the cutting process is much simpler.Furthermore,as the scale of the problem increases,the advantage of the calculation time and cutting process become more obvious,and the material utilization level difference decreases.Meanwhile,compare the proposed system with commercial software,various test data show that the proposed algorithm is more effective which has a higher material utilization level and simpler cutting process.