The semiconductor industry provides a host of very challenging problems in production planning and scheduling because of the unique features of the wafer fab. This research addresses the need to develop an approach, which can be used to generate optimal or near-optimal solutions to the scheduling problem of a wafer fab, by using Mathematical Programming for a general case of a wafer fab.

The problem is approached in two steps. First, the number of lots of different products to be released into the system during each planning period is determined, such that the total tardiness of the product orders is minimized over the planning horizon. Second, the schedule of these lots is determined so that the cycle time of each lot released into the system is minimized. Thus, the performance measures based both on due dates and cycle time are considered.

The lot release, tardiness problem is formulated as an integer linear program, and a 3-phase procedure, which utilizes a variation of the Wilkerson-Irwin algorithm, is developed. The performance of this 3-phase procedure is further improved by using insights from classical scheduling theory. The scheduling problem is formulated as a 0-1 integer linear program. An algorithm is developed for tightening the LP relaxation of this 0-1 integer linear programming model (of the scheduling problem) leading to a better performance of the branch and bound procedure used for its solution. Lagrangian relaxation is applied on a carefully chosen set of constraints in the scheduling problem, and a Lagrangian heuristic is developed for scheduling the jobs in each period of the planning horizon. Several useful insights are developed throughout to further improve the performance of the proposed algorithm.

Experiments are conducted for both the tardiness and the scheduling problems. Five experiments are conducted for the tardiness problem. Each experiment has a different combination of number of products, machines, and work orders in a small sized wafer fab (2 to 6 products, 8 to 10 station families, 15 to 30 workstations, 9 to19 work orders, and 100 to 250 lots per work order). The solutions obtained by the 3-phase procedure are compared to the optimal solutions of the corresponding tardiness problems, and the tardiness per work order for the 3-phase procedure is 0% to 25% greater than the optimal solution. But the time required to obtain the optimal solution is 22 to 1074 times greater than the time required to obtain the solution through the 3-phase procedure. Thus, the 3-phase procedure can generate almost optimal solutions and requires much smaller computation time than that required by the optimal solution.

Four experiments are conducted to test the performance of the scheduling problem. Each experiment has a different combination of number of products, machines, routes, bottleneck stations, processing times, and product mix entering the system each day in a small sized wafer fab (2 products, 8 station families, 18 workstations, and 8 to 10 lots released per day into the system). The solution quality of the schedule generated by the Lagrangian heuristic is compared to the solution provided by the standard dispatching rules available in practice. In each experiment, the cycle time of a product for each dispatching rule is divided by the best cycle time for that product over all the dispatching rules in that experiment. This ratio for the Lagrangian heuristic in each experiment and over all the experiments varies from 100% to 104%. For the standard dispatching rules, this ratio ranges from 100% to 120% in each experiment and also over all the experiments. The average of the ratio over all the experiments is the least for the Lagrangian heuristic. This indicates that for the experiments conducted, the Lagrangian heuristic consistently provides a solution that is, or is close to, the best solution and, hence, quite competitive when compared to the standard dispatching rules.