A Dynamic Programming Algorithm Based Improved Strip Packing Algorithm for Single-size PCB Packing Problem

Abstract

The two-dimensional rectangular material sheet packing problem has long been a tricky one in electric industry perplexing PCB manufacturers. In order to solve single-size rectangular PCB orthogonal packing problem, a dynamic programming method based improved strip packing algorithm (DISPA) was proposed. DISPA algorithm takes into consideration the wasted area generated when a strip is packed. If the fact occurs that the wasted areas of multiple strips meet the relaxed constraints, a dynamic programming procedure is adopted to calculate the potential packing number in the remaining sheet. And the strip with the largest total packing number will be adopted as the current operational decision. Before a strip is placed, an extreme point rule will be applied to position the strip and obtain other feasible extreme points. Hence, the follow-up process can run smoothly and effectively. According to the experimental results, DISPA algorithm has higher average utilization rate and packing number than dynamic programming algorithm, simplex algorithm and minimum-waste-area algorithm.