A heuristic algorithm for substrates testing in MCM

Multi-chip module (MCM) substrate is designed to pack two or more semiconductor chips. On a MCM substrate, there might exist a few types of faults in the wiring. Thus, it is essential to establish an efficient method for testing in MCM to detect faults. This paper presents a heuristic algorithm for substrates testing in MCM. Our objective is to minimize the completion time of the testing. The testing is performed by two equipments, called probe. Several previous works propose a method for the testing. Although the method finds at least one feasible solution fast, there is no guarantee that the solution is always good. Therefore, we formulate a testing problem as a shortest path problem with covering constraints (SPCC) and then, we propose a heuristic algorithm for the SPCC. In computation experiments, we show the SPCC approach are superior to the existing method.