Bin covering algorithms in the second stage of the lot to order matching problem

We formulate the problem of effectively assigning semiconductor fabrication wafer lots to customer orders of various sizes, or the lot-to-order matchi ng problem, as an integer programming problem. Our goal in this paper is to develop an efficient. practical method for solving this problem for variou s performance measures. Because of its complexity we decompose the problem into a knapsack problem coupled with a generalized bin-covering problem, an d solve these subproblems sequentially using heuristic methods. We restrict our attention to solution methods for the less-common second subproblem, a nd analyze the performance of several heuristics using a data set represent ative of real situations in a semiconductor back-end. Based on this analysi s, we show that these heuristics perform significantly better than current industrial practice in the context of the overall problem.