Vertex packing problem application to the design of electronic testing fixtures

In this paper, the authors report on the use of combinatorial optimization techniques to design testing fixtures for Printed Circuit Boards (PCBs). For testing the functionality of a PCB, nail-like testing devices (probes) on the surface of a testing fixture are brought in contact with prespecified test points (pads) on the surface of the PCB. The two design decisions for the testing fixture are: (a) to select from an available set of pads the ones to test (this determines the location of the probes on the fixture) subject to the restriction that in prespecified subsets of the set of pads (these subsets are referred to as ‘nets’) and a priori determined number of pads have to be tested (this is referred to as the ‘net restriction’), and (b) to choose the probe size to be used for testing each pad (only two available sizes: a large (100mil) and a small (50mil)) subject to the considerations that larger size probes are more reliable for testing purposes and probes that are assigned to pads in close proximity should not come in physical contact with each other (it creates short circuits and erroneous test results). Thus, the problem the testing engineer faces is to assign the maximum number of 100mil probes to an appropriately selected set of pads in a way that avoids the creation of short circuits and accounts for the ‘net restriction’. The authors develop an efficient algorithm to solve the problem using results from the vertex packing literature, which exploit the special structure of an appropriate geometric graph that can be defined in this application. The algorithm can handle the large size real problem within 2-3 minutes of real time on a microcomputer.