Probability analysis of the repairable queueing systemM/G(E k /H)/1

The repairable queueing system (RQS) in which the server has an exponential lifetime distribution has been studied in several articles [1–4]. Here, we deal with the new RQSM/G(E _k /H)/1 in which the lifetime distribution of the server is Erlangian. By forming a vector Markov process, i.e. by using the method of supplementary variables, we obtained some system characters, the reliability indices of the server, and the time distribution of a customer spent on the server. For this RQS, the generalized service time distribution of each customer will depend on the remainder life of the server. Based on this, a new kind of queues, for which the service time distributions are chosen by the customers in some stochastic manner, appears in queueing theory.Project supported by the National Natural Science Foundation of China.     

Implementation of Markovian Queueing Network Model with Multiple Closed Chains

Mathematical strategy portrays the performance evaluation of computer and communication system and it deals with the stochastic properties of the multiclass Markovian queueing system with class-dependent and server-dependent service times. An algorithm is designed where the job transitions are characterized by more than one closed Markov chain. Generating functions are implemented to derive closed form of solutions and product form solution with the parameters such as stability, normalizations constant and marginal distributions. For such a system with N servers and L chains, the solutions are considerably more complicated than those for the systems with one sub-chain only. In Multi-class queueing network, a job moves from a queue to another queue with some probability after getting a service. A multiple class of customer could be open or closed where each class has its own set of queueing parameters. These parameters are obtained by analyzing each station in isolation under the assumption that the arrival process of each class is a state-dependent Markovian process along with different service time distributions. An algorithmic approach is implemented from the generating function representation for the general class of Networks. Based on the algorithmic approach it is proved that how open and closed sub-chain interact with each other in such system. Specifically, computation techniques are provided for the calculation of the Markovian model for multiple chains and it is shown that these algorithms converge exponentially fast.     

Analysis of a Queueing Model with Batch Markovian Arrival Process and General Distribution for Group Clearance

In this paper we consider a single server queueing model with under general bulk service rule with infinite upper bound on the batch size which we call group clearance. The arrivals occur according to a batch Markovian point process and the services are generally distributed. The customers arriving after the service initiation cannot enter the ongoing service. The service time is independent on the batch size. First, we employ the classical embedded Markov renewal process approach to study the model. Secondly, under the assumption that the services are of phase type, we study the model as a continuous-time Markov chain whose generator has a very special structure. Using matrix-analytic methods we study the model in steady-state and discuss some special cases of the model as well as representative numerical examples covering a wide range of service time distributions such as constant, uniform, Weibull, and phase type.

     

The $$MMAP\left[ K \right]/PH\left[ K \right]/1$$ queues with a last-come-first-served preemptive service discipline

This paper studies two queueing systems with a Markov arrival process with marked arrivals and PH-distribution service times for each type of customer. Customers (regardless of their types) are served on a last-come-first-served preemptive resume and repeat basis, respectively. The focus is on the stationary distribution of queue strings in the system and busy periods. Efficient algorithms are developed for computing the stationary distribution of queue strings, the mean numbers of customers served in a busy period, and the mean length of a busy period. Comparison is conducted numerically between performance measures of queueing systems with preemptive resume and preemptive repeat service disciplines. A counter-intuitive observation is that for a class of service time distributions, the repeat discipline performs better than the resume one. This revised version was published online in June 2006 with corrections to the Cover Date.     

On Markov?CKrein characterization of the mean waiting time in M/G/K and other queueing systems

We propose a new research direction to reinvigorate research into better understanding of the M/G/K and other queueing systems??via obtaining tight bounds on the mean waiting time as functions of the moments of the service distribution. Analogous to the classical Markov?CKrein theorem, we conjecture that the bounds on the mean waiting time are achieved by service distributions corresponding to the upper/lower principal representations of the moment sequence. We present analytical, numerical, and simulation evidence in support of our conjectures.     

Continuity theorems for the M/M/1/n queueing system

In this paper continuity theorems are established for the number of losses during a busy period of the M/M/1/n queue. We consider an M/GI/1/n queueing system where the service time probability distribution, slightly different in a certain sense from the exponential distribution, is approximated by that exponential distribution. Continuity theorems are obtained in the form of one or two-sided stochastic inequalities. The paper shows how the bounds of these inequalities are changed if further assumptions, associated with specific properties of the service time distribution (precisely described in the paper), are made. Specifically, some parametric families of service time distributions are discussed, and the paper establishes uniform estimates (given for all possible values of the parameter) and local estimates (where the parameter is fixed and takes only the given value). The analysis of the paper is based on the level crossing approach and some characterization properties of the exponential distribution. Dedicated to Vladimir Mikhailovich Zolotarev, Victor Makarovich Kruglov, and to the memory of Vladimir Vyacheslavovich Kalashnikov.     

Quasi-birth-and-death Markov processes with a tree structure and the MMAP[K]/PH[K]/N/LCFS non-preemptive queue

This paper studies a multi-server queueing system with multiple types of customers and last-come-first-served (LCFS) non-preemptive service discipline. First, a quasi-birth-and-death (QBD) Markov process with a tree structure is defined and some classical results of QBD Markov processes are generalized. Second, the MMAP[K]/PH[K]/N/LCFS non-preemptive queue is introduced. Using results of the QBD Markov process with a tree structure, explicit formulas are derived and an efficient algorithm is developed for computing the stationary distribution of queue strings. Numerical examples are presented to show the impact of the correlation and the pattern of the arrival process on the queueing process of each type of customer.     

An approximate analysis of a cyclic server queue with limited service and reservations

In this paper, we examine a queueing problem motivated by the pipeline polling protocol in satellite communications. The model is an extension of the cyclic queueing system withM-limited service. In this service mechanism, each queue, after receiving service on cyclej, makes a reservation for its service requirement in cyclej + 1. The main contribution to queueing theory is that we propose an approximation for the queue length and sojourn-time distributions for this discipline. Most approximate studies on cyclic queues, which have been considered before, examine the means only. Our method is an iterative one, which we prove to be convergent by using stochastic dominance arguments. We examine the performance of our algorithm by comparing it to simulations and show that the results are very good.     

The Discrete-Time GI/Geo/1 Queue with Multiple Vacations

We study a discrete-time GI/Geo/1 queue with server vacations. In this queueing system, the server takes vacations when the system does not have any waiting customers at a service completion instant or a vacation completion instant. This type of discrete-time queueing model has potential applications in computer or telecommunication network systems. Using matrix-geometric method, we obtain the explicit expressions for the stationary distributions of queue length and waiting time and demonstrate the conditional stochastic decomposition property of the queue length and waiting time in this system.     

The Periodic BMAP/PH/c Queue

In queueing theory, most models are based on time-homogeneous arrival processes and service time distributions. However, in communication networks arrival rates and/or the service capacity usually vary periodically in time. In order to reflect this property accurately, one needs to examine periodic rather than homogeneous queues. In the present paper, the periodic BMAP/PH/c queue is analyzed. This queue has a periodic BMAP arrival process, which is defined in this paper, and phase-type service time distributions. As a Markovian queue, it can be analysed like an (inhomogeneous) Markov jump process. The transient distribution is derived by solving the Kolmogorov forward equations. Furthermore, a stability condition in terms of arrival and service rates is proven and for the case of stability, the asymptotic distribution is given explicitly. This turns out to be a periodic family of probability distributions. It is sketched how to analyze the periodic BMAP/M _t /c queue with periodically varying service rates by the same method.     

服务系统中位相型分布的随机比较

本文运用应用概率中的随机占优研究位相型(PH)分布的随机比较问题,具体给出在一阶、二阶随机占优下比较两个离散PH分布或两个连续PH分布的充分条件及充分必要条件。研究表明,比较两个离散PH分布可变性的条件与比较两个连续PH分布可变性的条件不同,在二阶随机占优意义下比较两个连续PH分布的条件与均值无关,而比较两个离散PH分布的条件与均值有关。本文的结果可用于研究PH分布的最小变异系数问题和可变性问题,也可用于研究带有PH到达间隔或PH服务的排队系统中到达过程或服务时间可变性对系统队长或等待时间的影响。     

Age Process, Workload Process, Sojourn Times, and Waiting Times in a Discrete Time SM[K]/PH[K]/1/FCFS Queue

In this paper, we study a discrete time queueing system with multiple types of customers and a first-come-first-served (FCFS) service discipline. Customers arrive according to a semi-Markov arrival process and the service times of individual customers have PH-distributions. A GI/M/1 type Markov chain for a generalized age process of batches of customers is introduced. The steady state distribution of the GI/M/1 type Markov chain is found explicitly and, consequently, the steady state distributions of the age of the batch in service, the total workload in the system, waiting times, and sojourn times of different batches and different types of customers are obtained. We show that the generalized age process and a generalized total workload process have the same steady state distribution. We prove that the waiting times and sojourn times have PH-distributions and find matrix representations of those PH-distributions. When the arrival process is a Markov arrival process with marked transitions, we construct a QBD process for the age process and the total workload process. The steady state distributions of the waiting times and the sojourn times, both at the batch level and the customer level, are obtained from the steady state distribution of the QBD process. A number of numerical examples are presented to gain insight into the waiting processes of different types of customers.AMS subject classification: 60K25, 60J10This revised version was published online in June 2005 with corrected coverdate     

Analysis of a time-limited service priority queueing system with exponential timer and server vacations

We consider a multi-class priority queueing system with a non-preemptive time-limited service controlled by an exponential timer and multiple (or single) vacations. By reducing the service discipline to the Bernoulli schedule, we obtain an expression for the Laplace-Stieltjes transform (LST) of the waiting time distribution via an iteration procedure, and a recursive scheme to calculate the first two moments. It is noted that we have to select embedded Markov points based on the service beginning epochs instead of the service completion epochs adopted for most of M/G/1 queueing analyses. Through the queue-length analysis, we obtain a decomposition form for the LST of the waiting time in each queue having the exhaustive service.      

On stochastic processes in a multilevel control bulk queueing system

This article analyzes some stochastic processes that arise in a bulk single server queue with continuously operating server, state dependent compound Poisson input flow and general state dependent service process. The authors treat the queueing process as a semi–regenerative process and obtain the invariant probability measure and the transient distribution for the embedded Markov chain. The stationary probability measure for the queueing process with continuous time parameter is found by using semi-regenerative techniques. The authors also study the input and output processes and establish ergodic theorems for some functionals of these processes. The results are obtained in terms of the invariant probability measure for the embedded process and the stationary measure for the queueing process with continuous time parameter     

A queueing system with linear repeated attempts,bernoulli schedule and feedback

We analyse a single-server retrial queueing system with infinite buffer, Poisson arrivals, general distribution of service time and linear retrial policy. If an arriving customer finds the server occupied, he joins with probabilityp a retrial group (called orbit) and with complementary probabilityq a priority queue in order to be served. After the customer is served completely, he will decide either to return to the priority queue for another service with probability ϑ or to leave the system forever with probability =1−ϑ, where 0≤ϑ<1. We study the ergodicity of the embedded Markov chain, its stationary distribution function and the joint generating function of the number of customers in both groups in the steady-state regime. Moreover, we obtain the generating function of system size distribution, which generalizes the well-knownPollaczek-Khinchin formula. Also we obtain a stochastic decomposition law for our queueing system and as an application we study the asymptotic behaviour under high rate of retrials. The results agree with known special cases. Finally, we give numerical examples to illustrate the effect of the parameters on several performance characteristics.     

GI\M\n系統中大量服务的排队过程

<正> §1.引言 我們知道,描述一个排队过程,需要三个因素:輸入过程,排队紀律,及服务机构.所謂GI|M|n,就是指这样的一个排队过程,它的 i)輸入过程,各顾客到来的时間区間的长度t相互独立、相同分布.其分布記     

Stability analysis of parallel server systems under longest queue first

We consider the stability of parallel server systems under the longest queue first (LQF) rule. We show that when the underlying graph of a parallel server system is a tree, the standard nominal traffic condition is sufficient for the stability of that system under LQF when interarrival and service times have general distributions. Then we consider a special parallel server system, which is known as the X-model, whose underlying graph is not a tree. We provide additional “drift” conditions for the stability and transience of these queueing systems with exponential interarrival and service times. Drift conditions depend in general on the stationary distribution of an induced Markov chain that is derived from the underlying queueing system. We illustrate our results with examples and simulation experiments. We also demonstrate that the stability of the LQF depends on the tie-breaking rule used and that it can be unstable even under arbitrary low loads.     

Markov-modulatedPH/G/1 queueing systems

We study a PH/G/1 queue in which the arrival process and the service times depend on the state of an underlying Markov chain J(t) on a countable state spaceE. We derive the busy period process, waiting time and idle time of this queueing system. We also study the Markov modulated E_K/G/1 queueing system as a special case.     

An efficient forward–reverse expectation-maximization algorithm for statistical inference in stochastic reaction networks

In this work, we present an extension of the forward–reverse representation introduced by Bayer and Schoenmakers (Annals of Applied Probability, 24(5):1994–2032, 2014) to the context of stochastic reaction networks (SRNs). We apply this stochastic representation to the computation of efficient approximations of expected values of functionals of SRN bridges, that is, SRNs conditional on their values in the extremes of given time intervals. We then employ this SRN bridge-generation technique to the statistical inference problem of approximating reaction propensities based on discretely observed data. To this end, we introduce a two-phase iterative inference method in which, during phase I, we solve a set of deterministic optimization problems where the SRNs are replaced by their reaction-rate ordinary differential equations approximation; then, during phase II, we apply the Monte Carlo version of the expectation-maximization algorithm to the phase I output. By selecting a set of overdispersed seeds as initial points in phase I, the output of parallel runs from our two-phase method is a cluster of approximate maximum likelihood estimates. Our results are supported by numerical examples.     

The cyclic queue and the tandem queue

We consider a closed queueing network, consisting of two FCFS single server queues in series: a queue with general service times and a queue with exponential service times. A fixed number \(N\) of customers cycle through this network. We determine the joint sojourn time distribution of a tagged customer in, first, the general queue and, then, the exponential queue. Subsequently, we indicate how the approach toward this closed system also allows us to study the joint sojourn time distribution of a tagged customer in the equivalent open two-queue system, consisting of FCFS single server queues with general and exponential service times, respectively, in the case that the input process to the first queue is a Poisson process.