This thesis proposes a computationally effective analytical approach to automated material handling system (AMHS) performance modeling for a simple closed loop AMHS, such as is typical in supporting a 300mm wafer fab bay. Discrete-event simulation can produce accurate assessments of the production performance, including the contribution by the AMHS. However, the corresponding simulation models are both expensive and time-consuming to construct, and require long execution times to produce statistically valid estimates. These attributes render simulation ineffective as a decision support tool in the early phase of system design, where requirements and configurations are likely to change often. We propose an alternative model that estimates the AMHS performance considering the possibility of vehicle-blocking. A probabilistic model is developed, based on a detailed description of AMHS operations, and the system is analyzed as an extended Markov chain. The model tracks the operations of all the vehicles on the closed-loop considering the possibility of vehicle-blocking. The resulting large-scale model provided reasonably accurate performance estimates; however, it presented some computational challenges. These computational challenges motivated the development of a second model that also analyzes the system as an extended Markov chain but with a much reduced state space because the model tracks the movement of a single vehicle in the system with additional assumptions on vehicle-blocking. Neither model is a conventional Markov Chain because they combine the conventional Markov Chain analysis of the AMHS operations with additional constraints on AMHS stability and vehicle-blocking that are necessary to provide a unique solution to the steady-state behavior of the AMHS. Based on the throughput capacity model, an approach is developed to approximate the expected response time of the AMHS to move requests. The expected response times are important to measure the performance of the AMHS and for estimating the required queue capacity at each pick-up station. The derivation is not straightforward and especially complicated for multi-vehicle systems. The approximation relies on the assumption that the response time is a function of the distribution of the vehicles along the tracks and the expected length of the path from every possible location to the move request location.

We provide contributions to two classical areas of queueing. The first part of this thesis focuses on finding new conditions for a Markov chain on a general state space to be Harris recurrent, positive Harris recurrent or geometrically ergodic. Most of our results show that establishing each property listed above is equivalent to finding a good enough feasible solution to a particular optimal stopping problem, and they provide a more complete understanding of the role Foster's criterion plays in the theory of Markov chains. The second and third parts of the thesis involve analyzing queues from a transient, or time-dependent perspective. In part two, we are interested in looking at a queueing system from the perspective of a customer that arrives at a fixed time t. Doing this requires us to use tools from Palm theory. From an intuitive standpoint, Palm probabilities provide us with a way of computing probabilities of events, while conditioning on sets of measure zero. Many studies exist in the literature that deal with Palm probabilities for stationary systems, but very few treat the non-stationary case. As an application of our main results, we show that many classical results from queueing (in particular ASTA and Little's law) can be generalized to a time-dependent setting. In part three, we establish a continuity result for what we refer to as jump processes. From a queueing perspective, we basically show that if the primitives and the initial conditions of a sequence of queueing processes converge weakly, then the corresponding queue-length processes converge weakly as well in some sense. Here the notion of convergence used depends on properties of the limiting process, therefore our results generalize classical continuity results that exist in the literature. The way our results can be used to approximate queueing systems is analogous to the way phase-type random variables can be used to approximate other types of random variables.

The Markov Chain Monte Carlo (MCMC) method has been widely used in practice since the 1950's in areas such as biology, statistics, and physics. However, it is only in the last few decades that powerful techniques for obtaining rigorous performance guarantees with respect to the running time have been developed. Today, with only a few notable exceptions, most known algorithms for approximately uniform sampling and approximate counting rely on the MCMC method. This thesis focuses on algorithms that use MCMC combined with an algorithm from optimization called simulated annealing, for sampling and counting problems. Annealing is a heuristic for finding the global optimum of a function over a large search space. It has recently emerged as a powerful technique used in conjunction with the MCMC method for sampling problems, for example in the estimation of the permanent and in algorithms for computing the volume of a convex body. We examine other applications of annealing to sampling problems as well as scenarios when it fails to converge in polynomial time. We consider the problem of randomly generating 0-1 contingency tables. This is a well-studied problem in statistics, as well as the theory of random graphs, since it is also equivalent to generating a random bipartite graph with a prescribed degree sequence. Previously, the only algorithm known for all degree sequences was by reduction to approximating the permanent of a 0-1 matrix. We give a direct and more efficient combinatorial algorithm which relies on simulated annealing. Simulated tempering is a variant of annealing used for sampling in which a temperature parameter is randomly raised or lowered during the simulation. The idea is that by extending the state space of the Markov chain to a polynomial number of progressively smoother distributions, parameterized by temperature, the chain could cross bottlenecks in the original space which cause slow mixing. We show that simulated tempering mixes torpidly for the 3-state ferromagnetic Potts model on the complete graph. Moreover, we disprove the conventional belief that tempering can slow fixed temperature algorithms by at most a polynomial in the number of temperatures and show that it can converge at a rate that is slower by at least an exponential factor.

The promising development of wireless technologies has brought in an increasing demand of multimedia traffic. Since various types of traffic are inherently distinct in bandwidth requirements, delay sensitivities, and error tolerances, an adequate bandwidth allocation scheme is essential for the limited radio resource to fulfill different QoS (quality of service) requirements in mobile wireless networks. In this dissertation, we present a generalized channel preemption scheme (the GCPM) and a jamming-based medium access control with dynamic priority adjustment (the JMDPA) for the two different medium access models of a mobile wireless network, grant/request-based and contention-based, respectively. In the proposed GCPM, a mobile call is identified by four parameters, call type, traffic class, channel requirement, and preemption ratio. To effectively reduce dropping probability, high-priority handoff calls are allowed to fully or partially preempt low-priority ongoing calls when the mobile network becomes congested. An analytical model with multi-dimensional Markov chains is introduced to simultaneously investigate the effect of full and partial preemptions on the performance of a mobile wireless network. On the other hand, the proposed JMDPA scheme prioritizes a mobile node with two priorities, local and global; both of the local and global priorities can be dynamically changed based on the outcome in every contention round. Thus, any possible starvation of low-priority traffic or any ineffective contention of high-priority traffic can be avoided. A multi-dimensional Markov model, together with the scalability analysis, is introduced to evaluate the performance of the proposed JMDPA. The analytical results provide very useful guidelines to tune the QoS parameters for supporting prioritized multimedia traffic.

Thesis (Ph. D.)--University of Washington, 2003. / Vita. Includes bibliographical references (leaves 178-195).

No description available.

In the emerging aield of molecular machines, a molecular ratchet is a chemical system that allows the positional displacement of a submolecular component of be captured and directionally released. In information ratchets, the track over which a Brownian particle is to be transported is able to respond to the particle’s position. By raising energetic barriers to translation selectively behind the particle, it is possible to move the particle in a forward direction. This Thesis describes the development of a series of chemically-­‐driven information ratchets based on rotaxane architectures. Acylation of the rotaxane thread presents an impassible kinetic barrier to macrocycle shuttling. The incorporation of chiral centres into the thread allows the macrocycle’s position to have an effect on the kinetics of acylation in a chiral environment, with the result that the macrocycle is transported by successive acylation reactions in a direction speciaied by the handedness of a chiral. In Chapter One the physical principles of molecular motors are examined. It is shown that molecular motors are a subset of the much broader class of “triangular” reactions investigated by Onsager in 1931. Progress in the exciting aield of artiaicial chemical ratchets and motors is reviewed, and the deep connections between molecular motors and the cyclic reaction networks postulated to explain the origin of biological homochirality are explored. Chapter Two describes the synthesis and operation of a three-­‐compartment rotaxane information ratchet in which the macrocycle can be transported along a thread in either direction depending on the handedness of a chiral catalyst. Internal mechanisms of operation are elucidated by treating the system as a hidden Markov process. Chapter Three describes the synthesis and operation of a second-­‐generation three-­‐compartment information ratchet. A comparison between this system and that of the previous chapter sheds light on the complicated trade-­‐offs between kinetics and thermodynamics when these molecular ratchets are operated. In Chapter Four the ongoing efforts to construct extended information ratchets, incorporating many repeat units, are described. The synthesis of a aive-­‐ compartment information ratchet proved unexpectedly difaicult owing to problems of solubility. A four-­‐compartment rotaxane was easier to synthesise. Preliminary aindings suggest that an information ratchet mechanism is operating in this four-­‐compartment system.

This thesis provides a study of various boundary problems for one and two dimensional random walks. We first consider a one-dimensional random walk that starts at integer-valued height k > 0, with a lower boundary being the x-axis, and on each step moving downward with probability q being greater than or equal to the probability of going upward p. We derive the variance and the standard deviation of the number of steps T needed for the height to reach 0 from k, by first deriving the moment generating function of T. We then study two types of two-dimensional random walks with four boundaries. A Type I walk starts at integer-valued coordinates (h; k), where0 < h < m and 0 < k < n. On each step, the process moves one unit either up, down, left, or right with positive probabilities pu, pd, pl, pr, respectively, where pu + pd + pl + pr = 1. The process stops when it hits a boundary. A Type II walk is similar to a Type I walk except that on each step, the walk moves diagonally, either left and upward, left and downward, right and downward, or right and upward with positive probabilities plu, pld, prd, pru, respectively. We mainly answer two questions on these two types of two-dimensional random walks: (1) What is the probability of hitting one boundary before the others from an initial starting point? (2) What is the average number of steps needed to hit a boundary? To do so, we introduce a Markov Chains method and a System of Equations method. We then apply the obtained results to a boundary problem involving two independent one-dimensional random walks and answer various questions that arise. Finally, we develop a conjecture to calculate the probability of a two-sided downward-drifting Type II walk with even-valued starting coordinates hitting the x-axis before the y-axis, and we test the result with Mathematica simulations

Various models driven by a hidden Markov chain in discrete or continuous time are developed to capture the stylised features of market variables whose levels or values constitute as the underliers of financial derivative contracts or investment portfolios. Since the parameters are switching regimes, the changes and developments in the economy as soon as they arise are readily reflected in these models. The change of probability measure technique and the EM algorithm are fundamental techniques utilised in the optimal parameter estimation. Recursive adaptive filters for the state of the Markov chain and other auxiliary processes related to the Markov chain are derived which in turn yield self-tuning dynamic financial models. A hidden Markov model (HMM)-based modelling set-up for commodity prices is developed and the predictability of the gold market under this setting is examined. An Ornstein-Uhlenbeck (OU) model with HMM parameters is proposed and under this set-up, we address two statistical inference issues: the sensitivity of the model to small changes in parameter estimates and the selection of the optimal number of states. The extended OU model is implemented on a data set of 30-day Canadian T-bill yields. An exponential of a Markov-switching OU process plus a compound Poisson process is put forward as a model for the evolution of electricity spot prices. Using a data set compiled by Nord Pool, we illustrate the vast improvements gained in incorporating regimes in the model. A multivariate HMM is employed as a framework in providing the solutions of two asset allocation problems; one involves the mean-variance utility function and the other entails the CVaR constraint. Finally, the valuation of credit default swaps highlights the important considerations necessitated by pricing in a regime-switching environment. Certain numerical schemes are applied to obtain approximations for the default probabilities and swap rates.

The aim of this study is to analyze regional disparities and to test the convergence hypothesis across the provinces of Turkey. The study also attempts to analyze the spatial spillovers in the growth process of the provinces. The analyses cover the 1987-2001 period. Two alternative methodologies are used in the analyses. First, the methodology of &amp / #946 / -convergence based on cross-sectional regressions is used and effects of spatial dependence are analyzed using spatial econometric techniques. Second, Markov chain analysis is used and spatial dependence is integrated using spatial Markov chains. Results of both methodologies signal nonexistence of convergence and existence of spatial spillovers in the growth process of provinces.