On Markovian decision models with a finite skeleton

We present a class of countable state space Markovian decision models that can be investigated by means of an associated finite-state, finite-action reduced model which we call the skeleton. In particular, we obtain a turnpike theorem for the original model (Theorem 2 in Section 5) from a known turnpike theorem for the reduced finite model. For illustration, we present in detail an application of this approach to an inventory model (re-establishing a known turnpike result) and sketch analogous results for a cash-balance model and a growth model.

---

Zusammenfassung Wir führen eine Klasse von Markovschen Entscheidungsmodellen mit abzählbarem Zustandsraum ein, die mittels eines verbundenen, reduzierten Modells mit endlichem Zustands- und Aktionsraum, welches wir das Skelett nennen, untersucht werden können. Insbesondere erhalten wir ein Turnpike Theorem für das ursprüngliche Modell (Theorem 2 im Abschnitt 5) von einem bekannten Turnpike Theorem für das reduzierte endliche Modell. Zur Erläuterung stellen wir im einzelnen eine Anwendung dieses Ansatzes für ein Lagerhaltungsmodell (Wiederherleitung eines bekannten Turnpike Ergebnisses) dar, und wir skizzieren analoge Ergebnisse für ein Kassenhaltungsmodell und ein Wachstumsmodell.

     

Consistency of perturbation analysis for a queue with finite buffer space and loss policy

The subject of discrete-event dynamical systems has taken on a new direction with the advent of perturbation analysis (PA), an efficient method for estimating the gradients of a steady-state performance measure, by analyzing data obtained from a single-simulation experiment in the time domain. A crucial issue is whether PA gives strongly consistent estimates, namely, whether average time-domain-based gradients converge, over infinite horizon, to the steady-state gradients. In this paper, we investigate this issue for a queue with a finite buffer capacity and a loss policy. The performance measure in question is the average amount of lost customers, as a function of the buffer's capacity, which is assumed to be continuous in our work. It is shown that PA gives strongly consistent estimates. The analysis uses a new technique, based on busy period-dependent inequalities. This technique may have possible extensions to analyses of consistency of PA for more general queueing systems.     

Stochastic stability for Markovian jump linear systems associated with a finite number of jump times

This paper deals with a stochastic stability concept for discrete-time Markovian jump linear systems. The random jump parameter is associated to changes between the system operation modes due to failures or repairs, which can be well described by an underlying finite-state Markov chain. In the model studied, a fixed number of failures or repairs is allowed, after which, the system is brought to a halt for maintenance or for replacement. The usual concepts of stochastic stability are related to pure infinite horizon problems, and are not appropriate in this scenario. A new stability concept is introduced, named stochastic τ-stability that is tailored to the present setting. Necessary and sufficient conditions to ensure the stochastic τ-stability are provided, and the almost sure stability concept associated with this class of processes is also addressed. The paper also develops equivalences among second order concepts that parallels the results for infinite horizon problems.     

Multi-state throughput analysis of a two-stage manufacturing system with parallel unreliable machines and a finite buffer

This paper models and analyzes the throughput of a two-stage manufacturing system with multiple independent unreliable machines at each stage and one finite-sized buffer between the stages. The machines follow exponential operation, failure, and repair processes. Most of the literature uses binary random variables to model unreliable machines in transfer lines and other production lines. This paper first illustrates the importance of using more than two states to model parallel unreliable machines because of their independent and asynchronous operations in the parallel system. The system balance equations are then formulated based on a set of new notations of vector manipulations, and are transformed into a matrix form fitting the properties of the Quasi-Birth–Death (QBD) process. The Matrix-Analytic (MA) method for solving the generic QBD processes is used to calculate the system state probability and throughput. Numerical cases demonstrate that solution method is fast and accurate in analyzing parallel manufacturing systems, and thus prove the applicability of the new model and the effectiveness of the MA-based method. Such multi-state models and their solution techniques can be used as a building block for analyzing larger, more complex manufacturing systems.     

Time dependent analysis of finite buffer fluid flows and risk models with a dividend barrier

Based on the matrix-analytic approach to fluid flows initiated by Ramaswami, we develop an efficient time dependent analysis for a general Markov modulated fluid flow model with a finite buffer and an arbitrary initial fluid level at time 0. We also apply this to an insurance risk model with a dividend barrier and a general Markovian arrival process of claims with possible dependencies in successive inter-claim intervals and in claim sizes. We demonstrate the implementability and accuracy of our algorithms through a set of numerical examples that could also serve as test cases for comparing other solution approaches.      

A decomposition method for approximate evaluation of continuous flow multi-stage lines with general Markovian machines

In this paper, a decomposition method for evaluating the performance of continuous flow lines with machines characterized by general Markovian fluid models and finite capacity buffers is proposed. This study uses the exact solution of general two-stage Markovian fluid models as a building block. Decomposition equations are provided to propagate the effect of partial and complete blocking and starvation phenomena throughout the system. A decomposition algorithm that solves the new decomposition equations is proposed. Numerical results prove the good accuracy of the developed method. In particular, a comparison with existing techniques shows that our method is generally more accurate, especially in the estimation of the average buffer levels. Moreover, additional information can be collected by the application of our approach which enables a deeper analysis of the system behavior. Finally, the generality of the approach allows for modeling and studying many different system configurations within a unique framework, also including several previously uninvestigated layouts.     

Convergence rate analysis of discrete-time Markovian jump systems

This paper is concerned with convergence rate analysis of a discrete-time Markovian jump linear system. First, two eigenvalue sets of some operator associated with the Markovian jump linear system are defined to characterize its stability. It is shown that the fastest and slowest convergence rate of the Markovian jump system can be determined by the eigenvalues having minimal modulus and maximal modulus, respectively. Finally, a linear matrix inequality based approach is established to design controllers such that the closed-loop system has a guaranteed convergence rate. A numerical example is carried out to illustrate the effectiveness of the proposed approach.     

Traffic processes in a class of finite Markovian queues

This paper exposes the stochastic structure of traffic processes in a class of finite state queueing systems which are modeled in continuous time as Markov processes. The theory is presented for theM/E _k /φ/L class under a wide range of queue disciplines. Particular traffic processes of interest include the arrival, input, output, departure and overflow processes. Several examples are given which demonstrate that the theory unifies many earlier works, as well as providing some new results. Several extensions to the model are discussed.     

Operator renewal theory for continuous time dynamical systems with finite and infinite measure

We develop operator renewal theory for flows and apply this to obtain results on mixing and rates of mixing for a large class of finite and infinite measure semiflows. Examples of systems covered by our results include suspensions over parabolic rational maps of the complex plane, and nonuniformly expanding semiflows with indifferent periodic orbits. In the finite measure case, the emphasis is on obtaining sharp rates of decorrelations, extending results of Gouëzel and Sarig from the discrete time setting to continuous time. In the infinite measure case, the primary question is to prove results on mixing itself, extending our results in the discrete time setting. In some cases, we obtain also higher order asymptotics and rates of mixing.     

The Markov modulated regulated Brownian motion: A second-order fluid flow model of a finite buffer

A second-order fluid flow model of a queue with finite capacity buffer and variable net input process is presented, based on the previous work of Karandikar and Kulkarni (1995). Queue length is modelled as a Brownian motion whose parameters are controlled by a finite state Markov chain. The process, termed a Markov modulated regulated Brownian motion (MMRBM), provides analytical solutions for steady state queue length distributions, overflow losses and idleness probabilities using boundary regulators. Applications of the model include queues with failure-prone servers and ATM statistical multiplexers with variable traffic loads. This revised version was published online in June 2006 with corrections to the Cover Date.     

Stability of a class of networked control systems with Markovian characterization

This paper studies the stability problem for a class of networked control systems (NCSs) with the plant being a Markovian jump system. The random delays from the sensor to the controller and from the controller to the actuator are modeled as two Markov chains. The necessary and sufficient conditions for the stochastic stability are established. The state-feedback controller gain that depends on not only the delay modes but also the system mode is obtained through the iterative linear matrix inequality approach. An illustrative example is presented to demonstrate the effectiveness of the proposed method.     

Predictors for stationary processes with finite generalized Markovian property

A theorem is proved which establishes the conditions for a Gaussian vector stationary process to be Markovian. For a stationary process with finite generalized Markov property we construct a vector Markov process whose first coordinate coincides with the given process. Applying our theorem to the vector process, we derive formulas for the linear predictor of a process with finite generalized Markov property.Translated from Statisticheskie Metody, pp. 82–90, 1980.I would like to acknowledge the helpful attention of P. N. Sapozhnikov.     

Transient analysis of a Markovian queue with deterministic rejection

We analyze the transient behavior of the M/M/1+D queue. Considering an Erlang distribution for customers’ waiting time, we approximate the real system by a Markov chain. We obtain the Laplace Transform of the transient probabilities in the approximated model and the Laplace transform of the main performance measures for the real system. We next analyze the busy period of this queue. One interesting insight is that the busy period of the unstable M/M/s queue has a finite coefficient of variation.     

Optimal maintenance of systems with Markovian mission and deterioration

We consider the maintenance of a mission-based system that is designed to perform missions consisting of a random sequence of phases or stages with random durations. A finite state Markov process describes the mission process. The age or deterioration process of the system is described by another finite state Markov process whose generator depends on the phases of the mission. We discuss optimal repair and optimal replacement problems, and characterize the optimal policies under some monotonicity assumptions. We also provide numerical illustrations to demonstrate the structure of the optimal policies.     

On multiserver feedback retrial queue with finite buffer

This paper deals with a multiserver feedback retrial queueing system with finite waiting position and constant retrial rate. This system is analyzed as a quasi-birth-and-death (QBD) process and the necessary and sufficient condition for stability of the system is investigated. Some important system performance measures are obtained using matrix geometric method. The effect of various parameters on the system performance measures are illustrated numerically. Finally, the algorithmic development of the full busy period for the model under consideration is discussed.     

Finite buffer vacation models under E-limited with limit variation service and Markovian arrival process

We consider a finite-buffer single server queue with single (multiple) vacation(s) and Markovian arrival process. The service discipline is E-limited with limit variation (ELV). Several other service disciplines like, Bernoulli scheduling, nonexhaustive and E-limited service can be treated as special cases of the ELV service.     

Efficiency and production rate of a transfer line with two machines and a finite storage buffer

A markov model for a transfer line with two unreliable machines separated by a finite storage size buffer is introduced. Service time distribution for the two machines is Erlang whereas failure and repair times are assumed to be exponential random variables. The paper presents an efficient method to solve analytically the steady state probabilities of the system. This method is independent of the buffer size. We also include in the paper a study of the behavior of some systems performance measures such as the efficiency of the two machines and the production rate of the system.