Dynamics

Recall that a Riemannian metric g on an open n-dimensional manifold 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 g is invariant under 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)}$.

Theorem 1   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é map and is constant with respect to changes in the ${\bf\em\tau_0}$'s.

Proof 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 df of this map has the form of a matrix with -1's in the ${\bf\em\tau_J}$ column, with 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 (n- 1)'s for every diagonal entry, and -1's for every off diagonal entry.

Corollary 1   Reentrant systems of this type do not have chaotic dynamics.

Proof behavior of differentiable dynamical systems are characterized by the exponential growth of certain tangent vectors under the action of the dynamics [2]. Under the hypothesis stated, the length of tangent vectors is preserved by the dynamics.

In the special case of reentrant systems with only two machines (i.e. 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é 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é map is constant at this q. We have proven the following.

Lemma 1   The Poincaré 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 1 or -1, where defined. When idle times are time until next available batch, the Poincaré map is also a piecewise linear map of the interval, with slopes 1, - 1 and 0.

A point ${\bf\em (q,\tau_0)}$ of a reentrant system is said to be recurrent if its orbit under the Poincaré 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 periodic if ${\bf\em f^t(q,\tau_0)=(q,\tau_0)}$ for some ${\bf\em t>0}$, and eventually periodic if ${\bf\em f^{t+s}(q,\tau_0)=f^t(q,\tau_0 )}$ for some ${\bf\em t,s>0}$.

Lemma 2   When idle times are time until next available batch, any recurrent point in the interior of an interval for which the Poincaré map has slope 0 is a periodic point.

Proof image of an interval on which 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 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 bottleneck if the 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.

Proposition 1   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.

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 [3] on the topic of interval exchange maps, which are maps of the interval which have slope ${\bf\em\pm 1}$ and which are invertible. The Poincaré 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.

Conjecture 1   Consider a reentrant system with two machines for which idle times are ${\bf\em\tau }$-independent (considered as a piecewise linear map f of the interval with slopes ${\bf\em\pm 1}$). There is a subset I consisting of the disjoint union of a finite number of subintervals satisfying f(I) = I and on which f is invertible and acts as an interval exchange map.

Proposition 2 (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}$.

The interval exchange maps on k subintervals on may be parameterized by partitions of [0,1) (i.e. by elements of the unit simplex in k-dimensions) and permutations on k symbols. The follow ing result shows that generic interval exchange maps essentially all have somewhat complicated dynamics.

Proposition 3 (Veech)   For Lebesgue a.e. (with respect to the k-simplex) interval exchange maps, Lebesgue measure is the unique invariant measure, and f is ergodic. In addition, if k is odd, for Lebesgue a.e interval exchange maps, f is weakly mixing.

Proof of weak mixing). Veech [6] shows that when 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 . But this is equivalent to weak mixing [7].