\documentstyle[twocolumn]{article} \pagestyle{empty} \textheight 24.0cm \textwidth 17.7cm \topmargin -0.5cm \oddsidemargin -0.8cm \evensidemargin 0.8cm \makeatletter \def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus -.2ex}{2.3ex plus .2ex}{\large\bf}} \def\subsection{\@startsection {subsection}{2}{\z@}{-3.25ex plus -1ex minus -.2ex}{1.5ex plus .2ex}{\bf}} \def\qed{\hfill \vrule height 7pt width 7pt depth 0pt \medskip} \def\im{{\rm im}\ } \def\supp{{\rm supp}\ } \def\rank{{\rm rank}\ } \def\proof{\noindent{\bf Proof}\ \ } \newtheorem{theorem}{Theorem} \newtheorem{definition}{Definition} \newtheorem{proposition}{Proposition} \newtheorem{lemma}{Lemma} \newtheorem{corollary}{Corollary} \newtheorem{conjecture}{Conjecture} \begin{document} \date{} \title{On the stability of reentrant manufacturing systems} \author{ Danielle Hanson, Dieter Armbruster and Tom Taylor\\ Department of Mathematics and \\ Center for Systems Science and Engineering Research\\ Arizona State University\\ Tempe, Arizona 85287-1804\\ \tt tom.taylor@asu.edu } \maketitle \thispagestyle{empty} \noindent{\bf Keywords:} re-entrant manufacturing systems, discrete event systems, queueing theory, dynamical systems, topological dynamics \begin{abstract} This paper considers a discrete event model of reentrant manufacturing systems, forgoing the usual Poisson process/stochastic queuing theory set-up in favor of deterministic dynamical systems theory. On the more theoretical side, results obtained include a restrictive characterization of the class of dynamical systems arising in this context, and a detailed description of the variety of orbit behaviors which can arise in the case of two-machine reentrant systems. Contrary to a conjecture of Beaumarriage and Kempf, chaotic behavior does not occur \end{abstract} \section{Introduction} A reentrant manufacturing system is a scheduling and queuing system which is a mathematical idealization of a semiconductor production plant. Discrete {\em lots} of semiconductor wafers undergo a series, typically a long series, of processing stages. Each stage consists of a variant of one of a few operations, e.g. doping, masking, deposition, etching, performed in {\em machines} of various types. When the lot is finished with all processing stages it becomes an {\em out}. When the lot has entered the plant, but not yet been processed, it is called an {\em in}. Ins and outs must balance over long time intervals if the {\em inventory} is to remain bounded. Different stages require different processing times, in general, even if the same type of operation is being performed. The term {\em reentrant} describes a situation in which machines are not dedicated to processing a single stage, but process specific different stages as needed. There may be a group of two or more machines which perform the same type of operation, hence the same set of processing stages. A simple reentrant system is indicated in figure 1 below.\\ \vspace{1.0in} {\begin{figure} \caption{A simple reentrant system} \vspace{1.0in} \end{figure}} Multiple lots at diverse stages may await processing by a specific machine, hence the choice of stage to process upon the event of a machine empty is a control parameter; we call a state feedback law for determining this choice a {\em scheduling policy}. For example, one common scheduling policy is the {\em pull policy} , which dictates that a machine should process the stage which is the closest to completion, assuming there is at least one batch of that type within the queues. Various scheduling policies have been investigated in simulation \cite{Beaumariage and Kempf},\cite{Kumar}, and shown greater or lesser {\em throughput}, which should be maximized, and {\em inventory} which should be minimized. The scheduling policy is implemented only at machine empty times: Machines may require a {\em batch size} of more than one lot to initiate processing, and are forced or chosen to {\em idle} if batch or scheduling requirements are not met. The dynamics of such reentrant systems have been observed in simulation to be complicated, even in the absence of such stochastic effects as set up times, machine breakdowns and operator availability. Beaumariage and Kempf \cite{Beaumariage and Kempf} observe sensitive dependence on initial conditions as one component of this complexity, and postulate chaotic behavior, as has been demonstrated in similar systems by Chase, Serrano and Ramadge \cite{Ramadge}. The length of an idle is also a control parameter. Idle time is typically taken to be next availability of a lot at the appropriate stage of processing. The rationale here is maximizing machine usage, i.e efficiency; however, nonlinear dynamical constraints may propigate machine idles in ways difficult to quantify. It is the goal of this paper to clarify the nature of these and other effects due to deterministic nonlinear structures; some of these may be demonstrated to be robust under stochastic or deterministic perturbations. \section{Modeling} A reentrant system with {\bf \em n} stages of processing and {\bf \em m} machines is modeled as follows.\\ ${\bullet}$ Queues {\bf \em $Q_1$ , $Q_2$ , ... , $Q_n$} with {\bf \em $Q_i$} dedicated to lots awaiting processing at the {\em i-th} stage.\linebreak ${\bullet}$ Non-negative integer values {\bf \em $q_i$}, the number of lots in {\bf \em $Q_i$}.\linebreak ${\bullet}$ Machines {\bf \em $M_A$ , $M_B$ , $M_C$ , ...} with machine {\bf \em $M_I$} occupancy characterized by: i) the integer {\bf \em $j_I$}, the stage currently occupying {\bf \em $M_I$}, taking values in a subset of ${\bf \em \{0,1,\ldots,n\}}$ (the value 0 denoting machine idle), ii) the integer {\bf \em $B_I$}, the batch size required by machine {\bf \em I}, which satisfies {\bf \em $1\leq B_I$}, iii) the real values {\bf \em $\tau_I$}, the remaining processing time for the batch in machine {\bf \em I}, satisfying ${\bf \em 0 \leq \tau_I \leq T_{j_{I}}}$ , where ${\bf \em T_i}$ denotes the full processing time of stage {\bf \em i}. \vspace{.15 in} The state of the reentrant system may be described by variables {\bf \em y =} ${\bf \em (q_1, ... , q_n, j_A, ... , j_I, ... , \tau_A, ... , \tau_I, ... )}$ ${\bf \em = (q,\tau)}$, where {\bf \em q =} ${\bf \em (q_1, ... , q_n, j_A, ... , j_I,...)}$ and ${\bf \em \tau }$ ${\bf \em =(\tau_A, ... , \tau_I, ... )}$, while the reentrant system itself is determined by a graph such as figure 1 above as well as the batch sizes ${\bf \em B_A , B_B . . .}$ and processing times ${\bf \em T_{j_{A}} , T_{j_{B}}...}$. As ins and outs must balance over a period of time, we model the reentrant system as closed; this is the linkage connecting ins and outs in figure 1.\footnote{The introduction of ins by other deterministic schedules may be described by a closed reentrant system framework by the introduction of fictitious machines with batch size and/or processing times designed to produce the desired schedule.} When all times ${\bf \em \tau_I}$ are positive, the discrete vector {\bf \em q} is unchanging, while each ${\bf \em \tau_I}$ evolves continuously according to flow ${\bf \em \tau_I \mapsto \tau_I-(t-t_0)}$ , where {\bf \em t} denotes the current time and ${\bf \em t_0 }$ the time of the most recent machine empty. The next time some variable ${\bf \em \tau_I}$ equals zero is the when machine {\bf \em I }finishes a batch and empties; this {\bf \em I } satisfies the inequality ${\bf \em \tau_I = min \{ \tau_A , \tau_B , . . . \}}$ At this machine empty time ${\bf \em q_{j_{I}+1}}$ is incremented by the batch size of machine {\bf \em I}, except when ${\bf \em j_I = n}$ , in which case ${\bf \em q_1}$ is incremented. At the same time, another queue ${\bf \em q_k}$ may be decremented by the batch size, while ${\bf \em j_I}$ takes the value {\bf \em k} as determined by the scheduling policy . For example in the case of the "pull" policy, ${\bf \em q_k}$ is decremented only if {\bf \em k} is the largest value for which ${\bf \em q_k \geq B_I}$ and which is processed by machine {\bf \em I}. When all machines are processing, or have just processed a batch, the set of vectors ${\bf \em \tau}$ at a given vector {\bf \em q} may be considered a {\bf \em m} -dimensional box (with {\bf \em m} the number of machines). The dimensions of the box are given by the {\bf \em m} processing times ${\bf \em \{T_{j_{A}},T_{j_{B}}, ...\}}$. The same representation also applies in the case that one or more of the machines is idleing, provided that the idle time is independent of ${\bf \em \tau}$. For example, this situation would correspond to a policy in which machines without an appropriate batch to process would idle for a fixed period of time, then idle again if there is still no batch. In this case some ${\bf \em j_I}$ (or ${\bf \em j_I}$'s) are equal to zero and ${\bf \em T_{j_I}}$ will represent the assigned idleing time. In this representation, the vectors ${\bf \em \tau_0}$ corresponding to at least one machine emptying or finish ing its idle are given by {\bf \em m} of the box's {\bf \em 2m} faces. In this way, a reentrant system may be thought of as a collection of as boxes glued together along edges in some complicated way determined by the scheduling policy, with constant flow dynamics on each box in which all of the ${\bf \em \tau_I}$'s are decreasing at the same rate. The representation of idles is somewhat different under a policy for which a machine idles only until a batch is available. The idle time for a given machine ${\bf \em M_J}$ depends on ${\bf \em \tau}$ as well as {\bf \em q} in this situation. For example, when the required number and type of lots are currently processing in machine ${\bf \em M_I}$, the remaining idle time ${\bf \em \tau_J}$ will be equal to ${\bf \em \tau_I}$; in particular the set of ${\bf \em \tau}$'s is constrained to lie within a {\bf \em m-1} dimensional subbox of the {\bf \em m}-dimensional box at {\bf \em q}. Also, as ${\bf \em \tau_J = \tau_I}$, they are constrained to be zero together, so that the set of ${\bf \em \tau_0}$'s in this case lies in a {\bf \em m-2} dimensional face of the subbox. In the more general case, when it may happen that the lots required by ${\bf \em M_J}$ are not yet being processed by any machine, the idleing time ${\bf \em \tau_J}$ will be an affine function of the form ${\bf \em T-\tau_I}$, where ${\bf \em T}$ depends on ${\bf \em \tau}$ and { \bf \em q} in a complicated way, which will generally depend on future values of {\bf \em q}, and hence on the policy. In all cases however, the length of time until the next empty is bounded, hence the set of vectors ${\bf \em \tau_0}$, with associated vectors {\bf \em q} determines a Poincar\'{e} cross section for the dynamics. The Poincar\'{e} map {\bf \em f} associated to this cross section is readily determined: a configuration ({\bf \em q}, ${\bf \em \tau_0}$) in which ${\bf \em \tau_J}$ is the smallest positive processing time will be mapped to the configuration ${\bf \em (\hat{q}, \tau_A-\tau_J , \tau_B-\tau_J , ... , \hat{\tau_I}= T_{\hat{j}_I}-\tau_J , ..., \hat{\tau}_J=0 , ... )}$, with {\bf \em \^{q} } determined by the scheduling policy. \section{Dynamics} Recall that a Riemannian metric {\bf \em g} on an open {\bf \em n}-dimensional manifold {\bf \em N} is given by a smooth choice of positive definite quadratic form ${\bf \em g_x}$ on each tangent space ${\bf \em T_xN}$, and that if ${\bf \em f:N\rightarrow N}$ is a smooth mapping, then {\bf \em g} is invariant under {\bf \em f} if for all ${\bf \em x\in N}$ and for any choice of vectors ${\bf \em u,v\in T_xN}$, ${\bf \em g_x(u,v)=g_{fx}(f_*u, f_*v)}$. \begin{theorem} Assume that the assignment of idle times is ${\bf \em \tau}$-independent. Then there is a Riemannian metric on (an open dense subset of) the set of all ${\bf \em (q,\tau_0)}$, which is invariant under the action of the Poincar\'{e} map and is constant with respect to changes in the ${\bf \em \tau_0}$'s. \end{theorem} \proof We have ${\bf \em f(q,\tau_A, ... , \tau_I=0, ... , \tau_J , ... ) }$ ${\bf \em =(\tau_A-\tau_J ,\tau_B-\tau_J , ... , \hat{\tau_I}. T_{\hat{j}_I}-\tau_J , \ldots\ ,\hat{\tau}_J=0 , ... )}$ . The differential {\bf \em df} of this map has the form of a matrix with {\bf \em -1}'s in the ${\bf \em \tau_J}$ column, with {\bf \em 1}'s on the diagonal except between the ${\bf \em t_I}$ and ${\bf \em t_J}$ columns, where the 1's are below or above the diagonal depending on ${\bf \em I< J}$ or vice versa. The set of such matricies has a unique invariant positive definite quadratic form having {\bf \em (n- 1)}'s for every diagonal entry, and {\bf \em -1}'s for every off diagonal entry. \begin{corollary} Reentrant systems of this type do not have chaotic dynamics. \end{corollary} \proof Chaotic behavior of differentiable dynamical systems are characterized by the exponential growth of certain tangent vectors under the action of the dynamics \cite{devaney}. Under the hypothesis stated, the length of tangent vectors is preserved by the dynamics. \vspace{.20in} In the special case of reentrant systems with only two machines (i.e. {\bf \em m=2}), we can say more. In particular, when idles are ${\bf \em \tau}$ independent the set of ${\bf \em \tau}$'s are two dimensional rectangles and the set of ${\bf \em \tau_0}$'s is one dimensional and a union of intervals. By concatenating these intervals in some manner, the Poincar\'{e} map may be considered as a map of the interval. As this map is constructed by following a constant flow (with slope equal to one) from one section of the boundary of a rectangle to another, it must be piecewise linear on a collection of subintervals. The slope of the linear components will be ${\bf \em \pm 1}$. Where the idle time is equal to the time of the next available batch, the next machine empty also coincides with the end of idle , hence the Poincar\'{e} map is constant at this {\bf \em q}. We have proven the following. \begin{lemma} The Poincar\'{e} map may be represented as a piecewise linear map of the interval. In the case that the assignment of idle times is ${\bf \em \tau}$- independent, the slopes are equal to {\bf \em 1} or {\bf \em -1}, where defined. When idle times are time until next available batch, the Poincar\'{e} map is also a piecewise linear map of the interval, with slopes {\bf \em 1}, {\bf \em - 1} and {\bf \em 0.} \end{lemma} A point ${\bf \em (q,\tau_0)}$ of a reentrant system is said to be {\bf \em recurrent} if its orbit under the Poincar\'{e} map, ${\bf \em \{(q,\tau_0),f(q,\tau_0),f^2(q,\tau_0),f^3(q,\tau_0), \ldots\} }$ , intersects any neighborhood of ${\bf \em (q,\tau_0)}$. A point ${\bf \em (q,\tau_0)}$ is said to be {\bf \em periodic} if ${\bf \em f^t(q,\tau_0)=(q,\tau_0)}$ for some ${\bf \em t>0}$, and {\bf \em eventually periodic} if ${\bf \em f^{t+s}(q,\tau_0)=f^t(q,\tau_0 )}$ for some ${\bf \em t,s>0}$. \begin{lemma} When idle times are time until next available batch, any recurrent point in the interior of an interval for which the Poincar\'{e} map has slope {\bf \em 0} is a periodic point.\end{lemma} \proof The image of an interval on which {\bf\em f} has slope zero is a single point. If a point in the interior of that interval is recurrent, then the orbit of that image point returns to that interval, hence after one more iteration of {\bf \em f} returns to that image point. A group of ${\bf \em \mu}$ machines ${\bf \em \{M_I\}_I}$ which process the same set of stages is said to be a {\bf \em bottleneck} if the {\em average processing rate} ${\bf \em \rho_I=(\sum_{j_I} T_{j_I})/(\mu B_I)}$ is greater for this group than any other. A bottleneck forces queues ${\bf \em q_i}$ downstream to zero, hence downstream machines ${\bf \em M_K}$ to idle, at least ${\bf \em (\rho_I-\rho_K)/\rho_I }$ proportion of the time. \begin{proposition} A reentrant system with a bottleneck and with idle until next available batch has only periodic and eventually periodic dynamics. There are only a finite number of periodic orbits. The set of periodic orbits is unchanged under small perturbations of the set of processing times. \end{proposition} On the other hand, simulations discussed in the next section indicate that reentrant systems which do not have or do not force idleing until next available batch seemingly need not have periodic dynamics, and when they do have periodic dynamics will typically have an infinite number of periodic orbits of the same period. We have guidance from the dynamical systems literature \cite {katok} on the topic of {\em interval exchange maps}, which are maps of the interval which have slope ${\bf \em \pm 1}$ and which are invertible. The Poincar\'e maps of two machine reentrant systems are not constrained to be invertible, but may have other constraints which are not yet understood. The following conjecture relating reentrant systems to interval exchange maps has been verified in all examples considered so far. \begin{conjecture} Consider a reentrant system with two machines for which idle times are ${\bf \em \tau}$-independent (considered as a piecewise linear map {\bf \em f} of the interval with slopes ${\bf \em \pm 1}$). There is a subset {\bf \em I} consisting of the disjoint union of a finite number of subintervals satisfying {\bf \em f(I) = I} and on which {\bf \em f} is invertible and acts as an interval exchange map. \end{conjecture} \begin{proposition}[Katok] Given an invertible, piecewise linear map of the unit interval with slopes ${\bf \em \pm 1}$ (i.e. an interval exchange map), the interval decomposes into the disjoint union of a finite number of points and collections of intervals ${\bf \em \{A_i\} }$ and ${\bf \em \{B_j\}}$. Each ${\bf \em A_i}$ consists of a union of intervals of periodic points, each interval is contained in the orbit of all other intervals in of ${\bf \em A_i}$ and consists of points with the same period, except in the case that the period is even, when the midpoint of each interval may have half the period of the rest of the interval. Each ${\bf \em B_j}$ consists of a union of intervals containing a full Lebesgue measure set of points whose orbit closures are equal to ${\bf \em B_j}$. \end{proposition} The interval exchange maps on {\bf \em k} subintervals on may be parameterized by partitions of {\bf \em [0,1)} (i.e. by elements of the unit simplex in {\bf \em k}-dimensions) and permutations on {\bf \em k} symbols. The follow ing result shows that generic interval exchange maps essentially all have somewhat complicated dynamics. \begin{proposition}[Veech] For Lebesgue a.e. (with respect to the {\bf \em k}-simplex) interval exchange maps, Lebesgue measure is the unique invariant measure, and {\bf \em f} is ergodic. In addition, if {\bf \em k} is odd, for Lebesgue a.e interval exchange maps, {\bf \em f} is weakly mixing. \end{proposition} \proof (of weak mixing). Veech \cite{veech} shows that when {\bf \em k} is odd, that the only eigenvector of the unitary operator ${\bf \em U_f}$ is the constant function, where ${\bf \em U_f}$ is given by ${\bf \em h(x)\mapsto h(fx)}$ for ${\bf \em h\in L^2[0,1)}$. But this is equivalent to weak mixing \cite{walters}. \section{Simulations} We have simulated a two-machine reentrant system to test and help develop our theory. We began with prime processing times 223 for stage 1, 53 for stage 2, 167 for stage 3, and 71 for stage 4. Under the push policy, as well as two other policies, we found periodic behavior in many cases. In the others, seeming ly aperiodic behavior was found, although simulation cannot distinguish between very long transients and true nonperiodic or quasiperiodic behavior. In all cases we found that transients ceases and periodic behavior begins when one machine's queues contained no batches. In other words, when one machine becomes a bottleneck, forcing the other machine to idle, the dynamics become periodic. The mostly-idle machine processes batches as soon as they enter the queues while the bottleneck machine works constantly and predictably according to the policy. This is as predicted by the theory described above. An interesting feature of these simulations is the length of the transient. When the bottleneck machine's processing times were decreased or increases, the transient lengthened or shortened, respectively. In fact, at close to balanced machine use, the transient length surpassed 100,000 for system load of 15 or 16 lots. The transient also increases when queue load increases, since it is longer before one machine empties its queues and the other becomes the bottleneck. We also introduced stochastic perturbation of processing times, adding a uniform random variable. Suprisingly, the dynamics was unchanged, suggesting no sensitive dependence on initial conditions. This phenomenon can perhaps be explained in terms of rigidity of periodic orbits for interval exchange maps. \begin{thebibliography}{1} \bibitem{Beaumariage and Kempf} T. Beaumariage and K. Kempf. \newblock The nature and origin of chaos in manufacturing systems. \newblock Intel Corporation-Internal Memo \bibitem{devaney} R.Devaney. \newblock {\em An introduction to chaotic dynamical systems.} \newblock Addison-Wesley, Reading, Mass. 1989 \bibitem{katok} A. Katok and B. Hasselblatt. \newblock {\em Introduction to the the modern theory of dynamnical systems.} \newblock Cambridge University Press, 1995 \bibitem{Kumar} P.R.Kumar. \newblock Re-Entrant Lines. \newblock Technical report, Coordinated Systems Laboratory, University of Illinois, Urbana, IL 1994 \bibitem{Ramadge} C. Chase, J. Serrano and P.J.Ramadge. \newblock Periodicity and Chaos from Switched Flow Systems: Contrasting Examples of Discretely Controled Continuous Systems. \newblock {\em IEEE Trans. on Automatic Control}, 38:70--83, 1993 \bibitem{veech} W. Veech. \newblock The metric theory of interval exchange transformations I: generic spectral properties. \newblock {\em American Journal of Mathematics}, 106:1331-1359, 1984 \bibitem{walters} P.Walters. \newblock {\em An introduction to ergodic theory}. \newblock Berlin, Heidelberg, New York, 1982 \end{thebibliography} \end{document}