Wafer Defect Inspection Optimization: Models, Analysis and Algorithms

The prevalence of electronic devices has propelled the tremendous growth of the semiconductor industry in the past half century. The manufacturing of semiconductor wafers is a long and delicate process, where defect points may occur and cause the failure of the entire circuit. As more advanced devices introduce tiny and harder-to-detect defects, improvements in wafer defect inspection technologies are highly desired by the industry. One promising direction is to optimize the positioning of inspection regions for the e-beam inspection tool, so as to cover all suspect defect points on a target area of a wafer while maximizing the throughput of the scan. To this end, we formulate this defect inspection optimization problem (DIOP) as a mixed integer linear programming (MILP) model, and enhance the formulation using variable reduction. To address the computational challenge of solving large-scale DIOP instances, we further propose three approximation methods with theoretical bounds, namely, a constant-factor approximation algorithm that provides heuristic solutions quickly, a polynomial-time approximation scheme (PTAS) that has a strong performance guarantee, and an MILP-based hybrid method that combines the PTAS framework and MILP formulation and is suitable for parallel computing by design. Numerical experiments on synthetic and industry instances show the efficiency and effectiveness of the proposed methods. Particularly, for large-scale instances, the hybrid algorithm is capable of generating near-optimal solutions with theoretical guarantees within practically acceptable computational time.