Institute for Systems Research Technical Reports

This research aims at developing and implementing simulation-based operations research techniques to facilitate System Control (through sensitivity analysis) and System Design (through optimization) for semiconductor manufacturing systems.

Sensitivity analysis for small changes in input parameters is performed using gradient estimation techniques. Gradient estimation methods are evaluated by studying the state of the art and comparing the finite difference method and simultaneous perturbation method by applying them to a stochastic manufacturing system. The results are compared with the gradients obtained through analytical queueing models. The finite difference method is implemented in a heterogeneous simulation environment (HSE)-based decision support tool for process engineers. This tool performs heterogeneous simulations and sensitivity analyses.

The gradient-based techniques used for sensitivity analysis form the building blocks for a gradient-based discrete stochastic optimization procedure. This procedure is applied to the problem of allocating a limited budget to machine purchases to achieve throughput requirements and minimize cycle time. The performance of the algorithm is evaluated by applying the algorithm on a wide range of problem instances.

Existing theory is expanded intwo directions: the semi-Markov case is considered, and non-irreduciblechains are considered. In particular, the analysis of the non-irreduciblecase is a significant addition to the literature, since many real-worldsystems do not exhibit irreducibility under all stationary Markov policies. Extension of existing results to the semi-Markovcase is significant because it requires the definition of a newdynamic programming equation and a technically challenging adaptation of the Perron-Frobeniuseigenvalue from the discrete time case.

In order to determine an optimal policy, new concepts in the classificationof Markov chains need to be introduced. This is because in thenon-irreducible case, the average risk sensitive cost objective function permits extremely unlikely events to exert a controlling influence on costs. We define equivalence classes of statescalled `strongly communicating classes' and formulate in terms of thema new characterization of the underlying structureof Markov Decision Problems and Markov chains.

In the risk sensitive case, the expected cost incurred prior to a stopping time with finite expected valuecan be infinite. For this reason, we introduce an assumption: reachability with finite cost. This is the fundamental assumptionrequired to achieve the major results of this thesis.

We explore existence conditions for an optimal policy, optimality equations,and behavior for large and small risk sensitivity parameter. (Onlynon-negative risk parameters are discussed in this thesis -- i.e. the risk averse and risk neutral cases, not the risk seeking case.) Ramificationsfor the risk neutral objective function are also analyzed.Furthermore, a simple solution technique we call `recursive computation'to find an optimal policy that isapplicable to small state spaces is described through examples.

The countable state space case is explored, and results that hold only for a finite state space are also presented. Other, relatedobjective functions such as sample path cost are analyzed and discussed.

We also explore finite time horizon semi-Markov problems, and present a general technique for solving them.We define a new objective function, the minimization of which is calledthe `deadline problem'. This is a problem in which the probability of reaching the goal state in a set period of time is maximized. We transform thedeadline problem objective function into an equivalent finite-horizonrisk sensitive objective function.

Stochastic optimization is a direct application of the above root finding problem if the SA is driven by a gradient estimate of steady state performance. We study the convergence properties of an SA driven by agradient estimator which observes an increasing number of samples from the Markov chain at each step of the SA's recursion. To show almost sure convergence to the optimizer, a framework of verifiable conditions is introduced which builds on the general SA conditions proposed for the root finding problem.

We also consider a difficulty sometimes encountered in applicationswhen selecting the set used in the projection operator of the SA algorithm.Suppose there exists a well-behaved positive recurrent region of the state process parameter space where the convergence conditions are satisfied; this being the ideal set to project on. Unfortunately, the boundaries of this projection set are not known a priori when implementing the SA. Therefore, we consider the convergence properties when the projection set is chosen to include regions outside the well-behaved region. Specifically, we consider an SA applied to an M/M/1 which adjusts the service rate parameter when the projection set includes parameters that cause the queue to be transient.

Finally, we consider an alternative SA where the recursion is driven by a sample average of observations. We develop conditions implying convergence for this algorithm which are based on a uniform large deviation upper bound and we present specialized conditions implyingthis property for finite state Markov chains.

Numericalexperiments on a queueing model with high-dimensional parameter vectorsdemonstrate orders of magnitude faster convergence using thesealgorithms over related $(N+1)$-Simulation finite difference analoguesand another two-simulation finite difference algorithm that updates incycles.

These gradient methods are of significant use in complex manufacturingsystems like semiconductor manufacturing systems where we havea large number of input parameters which affect the average total cycle time.These gradient estimation methods can estimate the impact thatthese input parameters have and identify theparameters that have the maximum impact on system performance.