A Lagrangian heuristic for minimising risk using multiple heterogeneous metrology tools

Motivated by the high investment and operational metrology cost, and subsequently the limited metrology capacity, in modern semiconductor manufacturing facilities, we model and solve the problem of optimally assigning the capacity of several imperfect metrology tools to minimise the risk in terms of expected product loss on heterogeneous production machines. In this paper, metrology tools can differ in terms of reliability and speed. The resulting problem can be reduced to a variant of the Generalized Assignment Problem (GAP), the Multiple Choice, Multiple Knapsack Problem (MCMKP). A Lagrangian heuristic, including multiple feasibility heuristics, is proposed to solve the problem that are tested on randomly generated instances.