This dissertation investigates a shift scheduling problem in semiconductor wafer fabrication. Based on the deterministic paradigm in which all parameters are assumed to be deterministic and known, a mixed event-based optimization model is developed where the objective of scheduling is to meet the target starts quantity defined for each product and process step as much as possible. In this model, the input-output variables for various process steps are formulated differently according to their processing time data.; The shift scheduling problem is an integer programming formulation. To solve it, Lagrangian relaxation and LP relaxation heuristics are proposed. Both heuristics consist of two step procedures: solving a relaxed optimization problem and running a deterministic simulation. A fast approximate solution is first sought for the hard-to-solve integer programming problem. Then, to obtain a more realistic and feasible schedule for the wafer fab, a simulation model is utilized by incorporating analytical results of the optimization model as an input for dispatching in the simulation model.; The comparison study shows that the LP relaxation heuristic outperforms FIFO and Least Slack dispatching rules. The execution time taken to solve LP relaxation problem is negligible for reasonable sizes of test data sets. It confirms our expectation that an optimization based dispatching procedure which utilizes the global information of fab status would provide better performance over other simple dispatching rules. The Lagrangian relaxation heuristic which decomposes the problem into several network subproblems by relaxing the coupling constraints achieves a slight improvement of the objective function value over LP relaxation, with the cost of much longer execution time. However, using a distributed computing environment, the overall execution time of the Lagrangian relaxation heuristic is reduced drastically as solutions of the subproblems could be obtained in parallel.
展开▼
