Introducing Covering Problems for the Electronic Wafer Test

Semiconductor manufacturing is an essential area of modern industry. Its yield is influenced by a wide variety of different factors, among them machining precision as well as scheduling and processing concerns. To minimize the amount of faulty products, the semiconductors are examined at several steps in the manufacturing process. This paper presents the wafer covering problem, an optimization problem that arises during the multi-site electrical wafer test. Foundational research in this area is minimal, which this paper aims to amend. Mathematical definitions are introduced for the underlying decision problem. An objective function is presented to minimize probe mark damage and increase manufacturing yield while considering test efficiency as well. The problem is analyzed and references to similar problems in the literature are drawn. It is shown that even the decision version is NP-complete, using a reduction from the well-known set covering problem. The paper concludes by presenting a suite of practically relevant test problems for use in further research. Optimal solutions for many of these test instances are calculated using a constraint satisfaction solver.