Single-Server Queues with Markov-Modulated Arrivals and Service Speed

This paper considers single-server queues with several customer classes. Arrivals of customers are governed by the underlying continuous-time Markov chain with finite states. The distribution of the amount of work brought into the system on arrival is assumed to be general, which may differ with different classes. Further, the service speed depends on the state of the underlying Markov chain. We first show that given such a queue, we can construct the corresponding new queue with constant service speed by means of a change of time scale, and the time-average quantities of interest in the original queue are given in terms of those in the new queue. Next we characterize the joint distribution of the length of a busy period and the number of customers served during the busy period in the original queue. Finally, assuming the FIFO service discipline, we derive the Laplace–Stieltjes transform of the actual waiting time distribution in the original queue.     

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.     

Analysis of GI/M/n/n queueing system with ordered entry and no waiting line

This paper deals with a multi-server, finite-capacity queuing system with recurrent input and no waiting line. The interarrival times are arbitrarily distributed whereas service times are exponentially distributed. Moreover, the servers are heterogeneous and independent of each other. Arriving customers choose the server with the lowest index number among the empty servers. When all servers are busy at a time of an arrival, that arrival must leave the system without being served. The semi-Markov process method is used to describe this model and embedded Markov chain of the process is obtained. Furthermore, the Laplace–Stieltjes transform of the distribution of interoverflow times is derived which is the main objective of the paper. Finally, it is offered a new formulation for the loss probability which provides more efficient and rapid calculation is proposed.     

Matrix Product-Form Solution for an LCFS-PR Single-Server Queue with Multiple Arrival Streams Governed by a Markov Chain

This paper considers a stationary single-server queue with multiple arrival streams governed by a Markov chain, where customers are served on an LCFS preemptive-resume basis. Service times of customers from each arrival stream are generally distributed and service time distributions for different arrival streams may be different. Under these assumptions, it is shown that the stationary joint distribution of queue strings representing from which arrival stream each customer in the system arrived and remaining service times of respective customers in the system has a matrix product-form solution, where matrices constituting the solution are given in terms of the infinitesimal generator of a certain Markov chain. Compared with the previous works, the result in this paper is more general in the sense that general service time distributions are allowed, and it has the advantage of computational efficiency. Note also that the result is a natural extension of the classical result for the LCFS-PR M/G/1 queue. Further, utilizing the matrix product-form solution, we derive a new expression of the vector Laplace–Stieltjes transform of the stationary distribution of unfinished work in the work-conserving single-server queue with multiple arrival streams governed by a Markov chain, which is given by the sum of matrix-geometric series.     

Analysis of a finite buffer model with two servers and two nonpreemptive priority classes

In this paper, we analyze a finite buffer queueing model with two servers and two nonpreemptive priority service classes. The arrival streams are independent Poisson processes, and the service times of the two classes are exponentially distributed with different means. One of the two servers is reserved exclusively for one class with high priority and the other server serves the two classes according to a nonpreemptive priority service schedule. For the model, we describe its dynamic behavior by a four-dimensional continuous-time Markov process. Applying recursive approaches we present the explicit representation for the steady-state distribution of this Markov process. Then, we calculate the Laplace–Stieltjes Transform and the steady-state distribution of the actual waiting times of two classes of customers. We also give some numerical comparison results with other queueing models.     

Single-Server Queue with Markov-Dependent Inter-Arrival and Service Times

In this paper we study a single-server queue where the inter-arrival times and the service times depend on a common discrete time Markov chain. This model generalizes the well-known MAP/G/1 queue by allowing dependencies between inter-arrival and service times. The waiting time process is directly analyzed by solving Lindley's equation by transform methods. The Laplace–Stieltjes transforms (LST) of the steady-state waiting time and queue length distribution are both derived, and used to obtain recursive equations for the calculation of the moments. Numerical examples are included to demonstrate the effect of the autocorrelation of and the cross-correlation between the inter-arrival and service times. An erratum to this article is available at .     

The Busy Period and the Waiting Time Analysis of a MAP/M/c Queue with Finite Retrial Group

Abstract

We concentrate on the analysis of the busy period and the waiting time distribution of a multi-server retrial queue in which primary arrivals occur according to a Markovian arrival process (MAP). Since the study of a model with an infinite retrial group seems intractable, we deal with a system having a finite buffer for the retrial group. The system is analyzed in steady state by deriving expressions for (a) the Laplace–Stieltjes transforms of the busy period and the waiting time; (b) the probabiliy generating functions for the number of customers served during a busy period and the number of retrials made by a customer; and (c) various moments of quantites of interest. Some illustrative numerical examples are discussed.     

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     

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

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

Waiting and sojourn times in a multi-server queue with mixed priorities

We consider a multi-server queue with K priority classes. In this system, customers of the P highest priorities (P<K) can preempt customers with lower priorities, ejecting them from service and sending them back into the queue. Service times are assumed exponential with the same mean for all classes. The Laplace–Stieltjes transforms of waiting times are calculated explicitly and the Laplace–Stieltjes transforms of sojourn times are provided in an implicit form via a system of functional equations. In both cases, moments of any order can be easily calculated. Specifically, we provide formulae for the steady state means and the second moments of waiting times for all priority classes. We also study some approximations of sojourn-time distributions via their moments. In a practical part of our paper, we discuss the use of mixed priorities for different types of Service Level Agreements, including an example based on a real scheduling problem of IT support teams.      

An <Emphasis Type="Italic">M</Emphasis><Superscript>[<Emphasis Type="Italic">X</Emphasis>]</Superscript>/<Emphasis Type="Italic">G</Emphasis>/1 retrial queue with server breakdowns and constant rate of repeated attempts

We consider an M ^[X]/G/1 retrial queue subject to breakdowns where the retrial time is exponential and independent of the number of customers applying for service. If a coming batch of customers finds the server idle, one of the arriving customers begins his service immediately and the rest joins a retrial group (called orbit) to repeat his request later; otherwise, if the server is busy or down, all customers of the coming batch enter the orbit. It is assumed that the server has a constant failure rate and arbitrary repair time distribution. We study the ergodicity of the embedded Markov chain, its stationary distribution and the joint distribution of the server state and the orbit size in steady-state. The orbit and system size distributions are obtained as well as some performance measures of the system. The stochastic decomposition property and the asymptotic behavior under high rate of retrials are discussed. We also analyse some reliability problems, the k-busy period and the ordinary busy period of our retrial queue. Besides, we give a recursive scheme to compute the distribution of the number of served customers during the k-busy period and the ordinary busy period. The effects of several parameters on the system are analysed numerically. I. Atencia’s and Moreno’s research is supported by the MEC through the project MTM2005-01248.     

A Queue with Semi-Markovian Batch Plus Poisson Arrivals with Application to the MPEG Frame Sequence

We consider a queueing system with a single server having a mixture of a semi-Markov process (SMP) and a Poisson process as the arrival process, where each SMP arrival contains a batch of customers. The service times are exponentially distributed. We derive the distributions of the queue length of both SMP and Poisson customers when the sojourn time distributions of the SMP have rational Laplace–Stieltjes transforms. We prove that the number of unknown constants contained in the generating function for the queue length distribution equals the number of zeros of the denominator of this generating function in the case where the sojourn times of the SMP follow exponential distributions. The linear independence of the equations generated by those zeros is discussed for the same case with additional assumption. The necessary and sufficient condition for the stability of the system is also analyzed. The distributions of the waiting times of both SMP and Poisson customers are derived. The results are applied to the case in which the SMP arrivals correspond to the exact sequence of Motion Picture Experts Group (MPEG) frames. Poisson arrivals are regarded as interfering traffic. In the numerical examples, the mean and variance of the waiting time of the ATM cells generated from the MPEG frames of real video data are evaluated.     

Multi-server queueing system with a generalized phase-type service time distribution as a model of call center with a call-back option

A multi-server queueing system with a Markovian arrival process and finite and infinite buffers to model a call center with a call-back option is investigated. If all servers are busy during the customer arrival epoch, the customer may leave the system forever or move to the buffer (such a customer is referred to as a real customer), or, alternatively, request for call-back (such a customer is referred to as a virtual customer). During a waiting period, a real customer can be impatient and may leave the system without service or request for call-back (becomes a virtual customer). The service time of a customer and the dial time to a virtual customer for a server have a phase-type distribution. To simplify the investigation of the system we introduce the notion of a generalized phase-type service time distribution. We determine the stationary distribution of the system states and derive the Laplace–Stieltjes transforms of the sojourn and waiting time distributions for real and virtual customers. Some key performance measures are calculated and numerical results are presented.     

Tandem queueing system with infinite and finite intermediate buffers and generalized phase-type service time distribution

A tandem queueing system with infinite and finite intermediate buffers, heterogeneous customers and generalized phase-type service time distribution at the second stage is investigated. The first stage of the tandem has a finite number of servers without buffer. The second stage consists of an infinite and a finite buffers and a finite number of servers. The arrival flow of customers is described by a Marked Markovian arrival process. Type 1 customers arrive to the first stage while type 2 customers arrive to the second stage directly. The service time at the first stage has an exponential distribution. The service times of type 1 and type 2 customers at the second stage have a phase-type distribution with different parameters. During a waiting period in the intermediate buffer, type 1 customers can be impatient and leave the system. The ergodicity condition and the steady-state distribution of the system states are analyzed. Some key performance measures are calculated. The Laplace–Stieltjes transform of the sojourn time distribution of type 2 customers is derived. Numerical examples are presented.     

Analysis of the queue-length distribution for the discrete-time batch-service Geo/G/1/K queue

In this paper, we consider a discrete-time finite-capacity queue with Bernoulli arrivals and batch services. In this queue, the single server has a variable service capacity and serves the customers only when the number of customers in system is at least a certain threshold value. For this queue, we first obtain the queue-length distribution just after a service completion, using the embedded Markov chain technique. Then we establish a relationship between the queue-length distribution just after a service completion and that at a random epoch, using elementary ‘rate-in = rate-out’ arguments. Based on this relationship, we obtain the queue-length distribution at a random (as well as at an arrival) epoch, from which important performance measures of practical interest, such as the mean queue length, the mean waiting time, and the loss probability, are also obtained. Sample numerical examples are presented at the end.     

Dynamic Routing and Admission Control in High-Volume Service Systems: Asymptotic Analysis via Multi-Scale Fluid Limits

Motivated by applications in telephone call centers, we consider a service system model with m customer classes and r server pools. The model is one with doubly stochastic arrivals, which means that the m-vector λ of instantaneous arrival rates is allowed to vary both temporally and stochastically. Two levels of dynamic control are considered: customers may be either blocked or accepted at the time of their arrival, and then accepted customers of each class must be routed, either immediately upon acceptance or after some period of waiting, to a server pool that is qualified to handle that class. Customers who are made to wait before commencement of their service are liable to defect. The objective is to minimize the expected sum of blocking costs, waiting costs and defection costs over a fixed and finite planning horizon. We consider an asymptotic parameter regime in which (i) the arrival rates, service rates and defection rates are uniformly accelerated by a large factor κ, then (ii) arrival rates are increased by an additional factor g(κ), and the number of servers in each pool is increased by g(κ) as well. This produces a separation of time scales, justifying a pointwise stationary stochastic fluid approximation for our original system model. In the stochastic fluid approximation, optimal admission control and routing decisions are determined by a simple linear program that uses the current arrival rate vector λ as data. We explain how to implement the fluid model's optimal control policy in our original service system context, and prove that the proposed implementation is asymptotically optimal in the first-order sense. AMS subject classification: 60K30, 90B15, 90B36     

A first passage time problem for spectrally positive Lévy processes and its application to a dynamic priority queue

We study a first passage time problem for a class of spectrally positive Lévy processes. By considering the special case where the Lévy process is a compound Poisson process with negative drift, we obtain the Laplace–Stieltjes transform of the steady-state waiting time distribution of low-priority customers in a two-class M/GI/1$M/GI/1$ queue operating under a dynamic non-preemptive priority discipline. This allows us to observe how the waiting time of customers is affected as the policy parameter varies.     

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.     

Start‐up class models in multiple‐class queues with N‐policy

In this paper, we consider multipleclass queueing systems with Npolicy in which the idle server starts service as soon as the number of customers in the startup class reaches threshold N. We consider the cases of FCFS and nonpreemptive priority. We obtain the Laplace–Stieltjes transform of the waiting times of each class of customers. We also show some results for the general behavior of such systems.