Combining mathematical programming and enhanced GRASP metaheuristics : an application to semiconductor manufacturing

textPlanning and scheduling in semiconductor manufacturing is a difficult problem due to long cycle times, a large number of operational steps, diversified product types, and low-volume high-mix customer demand. This research addresses several problems that arise in the semiconductor industry related to front-end wafer fabrication operations and back-end assembly and test operations. The mathematical models built for these problems turn out to be large-scale mixed integer programs and hard to solve with exact methods. The major contribution of this research is to combine mathematical programming with metaheuristics to find high quality solutions within the time limits imposed by the industrial engineers who oversee the fabrication and test facilities. In order to reduce the size of problems that arise in practice, it is common to cluster similar product types into groups that reflect their underlying technology. The first part of the research is aimed at developing a greedy randomized adaptive search procedure (GRASP) coupled with path relinking (PR) to solve the capacitated clustering problem. The model is generic and can be applied in many different situations. The objective is to maximize a similarity measure within each cluster such that the sum of the weights associated with the product types does not exceed the cluster capacity in each case. In phase I, both a heaviest weight edge (HWE) algorithm and a constrained minimum cut (CMC) algorithm are used to select seeds for initializing the clusters. Feasible solutions are obtained with the help of a self-adjusting restricted candidate list. In phase II, three neighborhoods are defined and explored using the following strategies: cyclic neighborhood search, variable neighborhood descent, and randomized variable neighborhood descent (RVND). The best solutions found are stored in an elite pool. In a post-processing step, PR coupled with local search is applied to the pool members to cyclically generate paths between each pair. The elite pool is updated after each iteration and the procedure ends when no further improvement is possible. After grouping the product types into technologies, a new model is presented for production planning in a high volume fab that uses quarterly commitments to define daily target outputs. Rather than relying on due dates and priority rules to schedule lot starts and move work in process through the shop, the objective is to minimize the sum of the deviations between the target outputs and finished goods inventory. The model takes the form of a large-scale linear program that is intractable for planning horizons beyond a few days. Both Lagrangian relaxation and Benders decomposition were investigated but each proved ineffective. As a consequence, a methodology was developed which was more tailored to the problem’s structure. This involved creating weekly subproblems that were myopic but could be solved to optimality within a few minutes, and then postprocessing the results with a decomposition algorithm to fully utilize the excessive machine time. The heart of the post-processor consists of a rescheduling algorithm and a dispatching heuristic. The third part of the research focuses on the combinatorial problem of machinetooling setup and lot assignments for performing back-end operations. A new model and solution methodology are presented aimed at maximizing the weighted throughput of lots undergoing assembly and test, while ensuring that critical lots are given priority. The problem is formulated as a mixed-integer program and solved again with a GRASP that makes use of linear programming. In phase I of the GRASP, machine-tooling combinations are tentatively fixed and lot assignments are made iteratively to arrive at a feasible solution. This process is repeated many times. In phase II, a novel neighborhood search is performed on a subset of good solutions found in phase I. Using a linear programming-Monte Carlo simulation-based algorithm, new machine-tooling combinations are identified within the neighborhood of the solutions carried over, and improvements are sought by optimizing the corresponding lot assignments.Engineering Mechanic