The Versatility of MMAP[K] and the MMAP[K]/G[K]/1 Queue

This paper studies a single server queueing system with multiple types of customers. The first part of the paper discusses some modeling issues associated with the Markov arrival processes with marked arrivals (MMAP[K], where K is an integer representing the number of types of customers). The usefulness of MMAP[K] in modeling point processes is shown by a number of interesting examples. The second part of the paper studies a single server queueing system with an MMAP[K] as its input process. The busy period, virtual waiting time, and actual waiting times are studied. The focus is on the actual waiting times of individual types of customers. Explicit formulas are obtained for the Laplace–Stieltjes transforms of these actual waiting times.     

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     

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.     

The M/G/1 Queue with Finite Workload Capacity

We consider the M/G/1 queueing system in which customers whose admission to the system would increase the workload beyond a prespecified finite capacity limit are not accepted. Various results on the distribution of the workload are derived; in particular, we give explicit formulas for its stationary distribution for M/M/1 and in the general case, under the preemptive LIFO discipline, for the joint stationary distribution of the number of customers in the system and their residual service times. Furthermore, the Laplace transform of the length of a busy period is determined. Finally, for M/D/1 the busy period distribution is derived in closed form.     

The Virtual Waiting Time of the M/G/1 Queue with Impatient Customers

The M/G/1 queue with impatient customers is studied. The complete formula of the limiting distribution of the virtual waiting time is derived explicitly. The expected busy period of the queue is also obtained by using a martingale argument.     

Asymptotic Behavior of Loss Probability in GI/M/1/K Queue as K Tends to Infinity

We obtain an asymptotic behavior of the loss probability for the GI/M/1/K queue as K for cases of <1, >1 and =1.     

Optimality of D-Policies for an M/G/1 Queue with a Removable Server

We consider an M/G/1 queue with a removable server. When a customer arrives, the workload becomes known. The cost structure consists of switching costs, running costs, and holding costs per unit time which is a nonnegative nondecreasing right-continuous function of a current workload in the system. We prove an old conjecture that D-policies are optimal for the average cost per unit time criterion. It means that for this criterion there is an optimal policy that either runs the server all the time or switches the server off when the system becomes empty and switches it on when the workload reaches or exceeds some threshold D.     

A matrix-analytic solution for the DBMAP/PH/1 priority queue

Priority queueing models have been commonly used in telecommunication systems. The development of analytically tractable models to determine their performance is vitally important. The discrete time batch Markovian arrival process (DBMAP) has been widely used to model the source behavior of data traffic, while phase-type (PH) distribution has been extensively applied to model the service time. This paper focuses on the computation of the DBMAP/PH/1 queueing system with priorities, in which the arrival process is considered to be a DBMAP with two priority levels and the service time obeys a discrete PH distribution. Such a queueing model has potential in performance evaluation of computer networks such as video transmission over wireless networks and priority scheduling in ATM or TDMA networks. Based on matrix-analytic methods, we develop computation algorithms for obtaining the stationary distribution of the system numbers and further deriving the key performance indices of the DBMAP/PH/1 priority queue. AMS subject classifications: 60K25 · 90B22 · 68M20 The work was supported in part by grants from RGC under the contracts HKUST6104/04E, HKUST6275/04E and HKUST6165/05E, a grant from NSFC/RGC under the contract N_HKUST605/02, a grant from NSF China under the contract 60429202.     

A note on the optimality of the N- and D-policies for the M/G/1 queue

This note considers the N- and D-policies for the M/G/1 queue. We concentrate on the true relationship between the optimal N- and D-policies when the cost function is based on the expected number of customers in the system.     

A BMAP/G/1 Retrial Queue with a Server Subject to Breakdowns and Repairs

In this paper, we consider a BMAP/G/1 retrial queue with a server subject to breakdowns and repairs, where the life time of the server is exponential and the repair time is general. We use the supplementary variable method, which combines with the matrix-analytic method and the censoring technique, to study the system. We apply the RG-factorization of a level-dependent continuous-time Markov chain of M/G/1 type to provide the stationary performance measures of the system, for example, the stationary availability, failure frequency and queue length. Furthermore, we use the RG-factorization of a level-dependent Markov renewal process of M/G/1 type to express the Laplace transform of the distribution of a first passage time such as the reliability function and the busy period.     

Analysis of the M X /G/1 Queue Under D-Policy

Abstract

We study the queue length of the M ^X /G/1 queue under D-policy. We derive the queue length PGF at an arbitrary point of time. Then, we derive the mean queue length. As special cases, M/G/1, M ^X /M/1, and M/M/1 queue under D-policy are investigated. Finally, the effects of employing D-policy are discussed.     

A Polynomial Factorization Approach for the Discrete Time GIX/>G/1/K Queue

This paper proposes a polynomial factorization approach for queue length distribution of discrete time GI ^X /G/1 and GI _X /G/1/K queues. They are analyzed by using a two-component state model at the arrival and departure instants of customers. The equilibrium state-transition equations of state probabilities are solved by a polynomial factorization method. Finally, the queue length distributions are then obtained as linear combinations of geometric series, whose parameters are evaluated from roots of a characteristic polynomial.     

N-策略休假GI-X／G／1排队系统队长的瞬时分布

本文应用Markov骨架过程理论研究了N-休假策略GI~X/G/1排队系统,并得到了队长的瞬时分布.     

A controlled M / G / 1 workload process with an application to perishable inventory systems

We derive the stationary distribution of the regenerative process W(t), t ≥ 0, whose cycles behave like an M / G / 1 workload process terminating at the end of its first busy period or when it reaches or exceeds level 1, and restarting with some fixed workload . The result is used to obtain the overflow distribution of this controlled workload process; we derive and , where T is the duration of the first cycle. W(t) can be linked to a certain perishable inventory model, and we use our results to determine the distribution of the duration of an empty period.D. Perry was supported by a Mercator Fellowship of the Deutsche Forschungsgemeinschaft.     

On the multi-phase M/G/1 queueing system with random feedback

In this paper we consider an M/G/1 queue with k phases of heterogeneous services and random feedback, where the arrival is Poisson and service times has general distribution. After the completion of the i-th phase, with probability θ _i the (i + 1)-th phase starts, with probability p _i the customer feedback to the tail of the queue and with probability 1 − θ _i − p _i  = q _i departs the system if service be successful, for i = 1, 2 , . . . , k. Finally in kth phase with probability p _k feedback to the tail of the queue and with probability 1 − p _k departs the system. We derive the steady-state equations, and PGF’s of the system is obtained. By using them the mean queue size at departure epoch is obtained.     

Analysis of the M/M/1 Queue with Processor Sharing via Spectral Theory

We show in this paper that the computation of the distribution of the sojourn time of an arbitrary customer in a M/M/1 with the processor sharing discipline (abbreviated to M/M/1 PS queue) can be formulated as a spectral problem for a self-adjoint operator. This approach allows us to improve the existing results for this queue in two directions. First, the orthogonal structure underlying the M/M/1 PS queue is revealed. Second, an integral representation of the distribution of the sojourn time of a customer entering the system while there are n customers in service is obtained.     

Analysis of M/G/1-Queues with Setup Times and Vacations under Six Different Service Disciplines

Single server M/G/1-queues with an infinite buffer are studied; these permit inclusion of server vacations and setup times. A service discipline determines the numbers of customers served in one cycle, that is, the time span between two vacation endings. Six service disciplines are investigated: the gated, limited, binomial, exhaustive, decrementing, and Bernoulli service disciplines. The performance of the system depends on three essential measures: the customer waiting time, the queue length, and the cycle duration. For each of the six service disciplines the distribution as well as the first and second moment of these three performance measures are computed. The results permit a detailed discussion of how the expected value of the performance measures depends on the arrival rate, the customer service time, the vacation time, and the setup time. Moreover, the six service disciplines are compared with respect to the first moments of the performance measures.     

M/G/1排队论系统的渐近稳定性

通过M/G/1算子的谱分析得到了M/G/1排队论系统的渐近稳定性.首先,将系统方程转化为某一合适Banach空间上的抽象Cauchy闻题,从而引入M/G/1算子.其次,分析了M/G/1算子的谱分布,得到了0是M/G/1算子的简单本征值且M/G/1算子的谱分布在左半平面的结果.最后,利用谱分析结果和算子半群理论得到了M/...     

Conditions for finite moments of waiting times inG/G/1 queues

We find conditions for E(W ) to be finite whereW is the stationary waiting time random variable in a stableG/G/1 queue with dependent service and inter-arrival times.Supported in part by KBN under grant 640/2/9, and at the Center for Stochastic Processes, Department of Statistics at the University of North Carolina Chapel Hill by the Air Force Office of Scientific Research Grant No. 91-0030 and the Army Research Office Grant No. DAAL09-92-G-0008.     

Stationary distribution of queue length in G / M / 1 queue with two-stage service policy

We consider a G / M / 1 queue with two-stage service policy. The server starts to serve with rate of μ₁ customers per unit time until the number of customers in the system reaches λ. At this moment, the service rate is changed to that of μ₂ customers per unit time and this rate continues until the system is empty. We obtain the stationary distribution of the number of customers in the system.