Vertex packing problem application to the design of electronic testing fixtures

In this paper, we 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 prespectified 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 (100 mil) and a small (50 mil)) 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 result). Thus, the problem the testing engineer faces is to assign the maximum number of 100 mil probes to an appropriately selected set of pads in a way that avoids the creation of short circuits and accounts for the "net restriction". We 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 we can define in this application. The algorithm can handle the large size real problem within 2-3 minutes of real time on a microcomputer.