(61e) Scheduling Complex Job-Shop with Re-Entrant Flow as Partially Observable Markov Decision Process (Pomdp) – Application to Semi-Conductor Manufacturing

Machine performance in most real world manufacturing environments, deteriorates with time, and maintenance is, in general, expensive. This means, in certain cases, the rate, at which defects are produced, keeps increasing with time unless the machine is serviced. Also, at times, the degradation in performance can only be gauged by the defect rate which calls for frequent testing. In a setting where the product is expensive and testing is time consuming, it is economically not viable to lose products as defective dies, or test each and every product. One typical example of such a setting is semiconductor wafer manufacturing facility, which is treated as the target application in this work. Although the concepts developed are fairly general and have wider applications.

A semiconductor wafer fab comes with its own complexities like large and changing varieties of products, sequence dependent set-up times, re-entrant process flow, etc., in a dynamic scheduling environment. This problem has been investigated from a variety of perspectives like heuristic rules, mathematical programming techniques, neighborhood search methods, and artificial intelligence techniques. In this study, we employ the use of rigorous probability theories and dynamic programming to account for the uncertainties inherent to the problem.

One of the bottlenecks or performance governing factors in the manufacturing assembly is the tool group/machine facilitating re-entrant flow. Therefore, the proposed work is an attempt to capture process drift (degradation in machine performance) in a single work-station, intermittent testing, and re-entrant flow in an optimization framework. The mentioned three factors are related to each other in more than one ways. The process drift calls for an optimal maintenance schedule; the long or expensive testing, calls for a good test or sampling policy; and re-entrant flow calls for optimal scheduling of the jobs at different stages of operation, yet competing for the same resources. Convoluted as it sounds, is the fundamental relationship between these factors. The machine maintenance and job-release schedule together affect the defect rate and product mix in the end, while sampling policy affects defect detection and the ability to device a good maintenance schedule. In semiconductor manufacturing, operation increases the value of the product much more than the raw material cost, and thus, need arises to save runs that are wasted on the defective dies. Especially in re-entrant flow setting, if a defect is inevitable, it better occur to the product in early stages of operation, since the product gathers value after every operation. Early detection of defects is as important. The relative importance of these cost heads is of course governed by the physical costs of maintenance, testing and product price respectively.

In the proposed work, all these complex factors are unified in an Approximate Dynamic Programming (ADP) [3] framework and discounted infinite horizon profit is maximized. The machine performance is approximated by a Markov model. Since a lot of information is not available (more precisely, not observed), this analysis results in a partially observable Markov decision process (POMDP). Only that it is way too big to be solved by analytical methods proposed in existing literature on POMDPs [1,2]. So, ADP is adapted to account for the partially observable nature of the problem.

Seeing the large size of the problem, we also propose a two-tier optimization methodology. The maintenance schedule directly affects the job-scheduling decision, while reverse is not true as long as the products are considered pretty similar to each other in terms of the wear they cause to the machine. The link between the two that goes both ways is the sampling policy. Therefore, at first, optimization is performed on the machine model to device an optimal maintenance schedule and reasonable sampling policy using a recursive Bayesian approach. The results are then used to develop optimal job release schedule, and sampling policy is refined simultaneously, to achieve the economic end.

The analysis, develops computational tools, on the way, concerning solution to large size POMDPs and gives prescriptions on the optimal (or near optimal) machine maintenance schedule, sampling policy and job-release schedule to re-entrant lines.

[1] Michael L. Lettman, Anthony R. Cassandra, and Leslie Pack Kaelbling. An efficient algorithm for dynamic programming in partially observable Markov decision processes. Technical Report CS-95-19, Brown University, Providence, Rhode Island, 1995.

[2] Chelsa C. White, III. Partially observed Markov decision processes. A survey. Annals of Operation Research, 32, 1991.

[3] J Choi, M.J. Realff, and J.H. Lee. Dynamic programming in a heuristically confined state space: a stochastic resource-constrained project scheduling application, Computers and Chemical Engineering, June 2004