Simulation methods for queues: An overview

This paper gives an overview of those aspects of simulation methodology that are (to some extent) peculiar to the simulation of queueing systems. A generalized semi-Markov process framework for describing queueing systems is used through much of the paper. The main topics covered are: output analysis for simulation of transient and steady-state quantities, variance reduction methods that exploit queueing structure, and gradient estimation methods for performance parameters associated with queueing networks.The research of this author was supported by the U.S. Army Research Office under Contract DAAG29-84-K-0030.The research of this author was supported by the U.S. Army Research Office under Contract DAAG29-84-K-0030 and National Science Foundation Grant DCR-85-09668.     

Entropy Maximization for Markov and Semi-Markov Processes

The literature about maximum of entropy for Markov processes deals mainly with discrete-time Markov chains. Very few papers dealing with continuous-time jump Markov processes exist and none dealing with semi-Markov processes. It is the aim of this paper to contribute to fill this lack. We recall the basics concerning entropy for Markov and semi-Markov processes and we study several problems to give an overview of the possible directions of use of maximum entropy in connection with these processes. Numeric illustrations are presented, in particular in application to reliability.     

The effect of information in separable Bayesian semi-Markov control models and its application to investment planning

We consider a separable Bayesian semi-Markov control model to describe economic decisions under uncertainty. Our main interest is to examine the influence of the possibility of learning on the economic decisions and on the total expected return in a multi-period framework. We make use of the concept of Blackwell-sufficiency and apply the results to multi-period investment planing under uncertainty.     

A Versatile Stochastic Maintenance Model with Reserve and Super-Reserve Machines

This article analyzes the maintenance of production system with unreliable machines. This system includes a repair facility and three types of unreliable machines: the main facility of working and reserve machines, and an auxiliary facility of super-reserve machines. Operating times of working machines are exponentially distributed. Upon failure, a working machine is immediately replaced by reserve machines available. Defective machines line up for repair, whose duration is arbitrarily distributed. Refurbished machines return to the main facility. If the main facility is restored to its original quantity (i.e., all machines are intact), the repair facility leaves on routine maintenance; all w+1 reserve machines are temporarily blocked and renewals come from the super-reserve group until the latter becomes exhausted. Then, the busy period is regenerated. The techniques include two-variate Markov and semi-regenerative processes, and a duality principle, to find the probability distribution of the number of intact machines. Explicit formulas obtained demonstrate a relatively effortless use of functionals of the main stochastic characteristics (such as expenses due to repair, maintenance, waiting, and rewards for higher reliability) and optimization of their objective function. Applications of such models include computer networking, human resources, and manufacturing processes.     

Diffusion Approximation in Overloaded Switching Queueing Models

The asymptotic behavior of a queueing process in overloaded state-dependent queueing models (systems and networks) of a switching structure is investigated. A new approach to study fluid and diffusion approximation type theorems (without reflection) in transient and quasi-stationary regimes is suggested. The approach is based on functional limit theorems of averaging principle and diffusion approximation types for so-called Switching processes. Some classes of state-dependent Markov and non-Markov overloaded queueing systems and networks with different types of calls, batch arrival and service, unreliable servers, networks (M _SM,Q /M _SM,Q /1/) ^r switched by a semi-Markov environment and state-dependent polling systems are considered.     

A computational procedure for the asymptotic analysis of homogeneous semi-Markov processes

A new algorithm for classifying the states of a homogeneous Markov chain having finitely many states is presented, which enables the investigation of the asymptotic behavior of semi-Markov processes in which the Markov chain is embedded. An application of the algorithm to a social security problem is also presented.     

Call Admission: A New Approach to Quality of Service

Quality of service guarantees are an important and much discussed aspect of ATM network design. However, there is no standard definition of quality of service. Moreover, some often-used criteria seem quite crude. We consider call admission to a bufferless ATM multiplexer with on/off sources. A new criterion for a guarantee on average cell loss is proposed. This criterion represents the quality of service from the point of view of the user, and is thus more reliable. We calculate the optimal policy that minimizes blocking subject to the guarantee, when there is only one type of user.The measure of cell-loss we propose is applicable to a wide range of models. It gives rise to a mathematical programming formulation, which we derive explicitly for our case.     

基于半马尔科夫过程的逻辑门可靠性分析

动态故障树分析方法是在静态故障树的基础上拓展而来的自上而下的图形化演绎技术,可以很好地对具有复杂失效行为和交互作用的系统进行建模,进而分析系统的可靠性。本文从动态故障树逻辑门的可靠性建模与分析入手,结合半马尔科夫过程原理,将动态逻辑门转化为半马尔科夫链。其次给出在半马尔科夫链中动态逻辑门输出事件的发生概率和系统可靠性的计算公式。提出各种逻辑门到半马尔科夫链的通用转化模型,通过更改通用模型中的相关参数,将逻辑门转化为半马尔科夫链。最后,基于半马尔科夫过程求解动态逻辑门输出事件的发生概率,以动态优先与门、顺序相关门和备件门为例,并给出系统可靠性的计算公式。     

Optimal stopping time on discounted semi-Markov processes

This paper attempts to study the optimal stopping time for semi- Markov processes (SMPs) under the discount optimization criteria with unbounded cost rates. In our work, we introduce an explicit construction of the equivalent semi-Markov decision processes (SMDPs). The equivalence is embodied in the expected discounted cost functions of SMPs and SMDPs, that is, every stopping time of SMPs can induce a policy of SMDPs such that the value functions are equal, and vice versa. The existence of the optimal stopping time of SMPs is proved by this equivalence relation. Next, we give the optimality equation of the value function and develop an effective iterative algorithm for computing it. Moreover, we show that the optimal and ε-optimal stopping time can be characterized by the hitting time of the special sets. Finally, to illustrate the validity of our results, an example of a maintenance system is presented in the end.     

On mean reward variance in semi-Markov processes

As an extension of the discrete-time case, this note investigates the variance of the total cumulative reward for the embedded Markov chain of semi-Markov processes. Under the assumption that the chain is aperiodic and contains a single class of recurrent states recursive formulae for the variance are obtained which show that the variance growth rate is asymptotically linear in time. Expressions are provided to compute this growth rate.