A Regularly Preemptive Model and its Approximations

A regularly preemptive model D,MAP/D ₁,D ₂/1 is studied. Priority customers have constant inter-arrival times and constant service times. On the other hand, ordinary customers' arrivals follow a Markovian Arrival Process (MAP) with constant service times. Although this model can be formulated by using the piecewise Markov process, there remain some difficult problems on numerical calculations. In order to solve these problems, a novel approximation model MAP/MR/1 with Markov renewal services is proposed. These two queueing processes become different due to the existence of idle periods. Thus, a MAP/MR/1 queue with a general boundary condition is introduced. It is a model with the exceptional first service in each busy period. In particular, two special models are studied: one is a warm-up queue and the other is a cool-down queue. It can be proved that the waiting time of ordinary customers for the regular preemption model is stochastically smaller than the waiting time of the former model. On the other hand, it is stochastically larger than the waiting time of the latter model.     

Discrete-time analysis of a classified multi-server queue with burst arrivals and a shared buffer

We study a discrete-time, classified multi-server queue with a shared buffer. There arem servers and each server belongs to one ofk classes (mk), so thatk kinds of jobs can be served in the system. We characterize a bursty arrival process using bursts which consist of the same kind of jobs. Once the first job of a burst arrives at the queue, the successive jobs will arrive on every time slot until the last job of the burst arrives. The numbers of jobs of a burst and the inter-arrival times of bursts are assumed to be i.i.d., respectively, and the service time is assumed to be equal to one slot. We propose an efficient numerical method to exactly obtain the job loss probability, the waiting time distribution and the mean queue length. We apply this model to the ATM switch with a shared buffer and obtain the performance measures. Numerical results show the advantage of the ATM switch with a shared buffer compared to the one with output buffers.     

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.     

Fitting correlated arrival and service times and related queueing performance

In this paper, we consider a queue where the inter-arrival times are correlated and, additionally, service times are also correlated with inter-arrival times. We show that the resulting model can be interpreted as an MMAP[K]/PH[K]/1 queue for which matrix geometric solution algorithms are available. The major result of this paper is the presentation of approaches to fit the parameters of the model, namely the MMAP, the PH distribution and the parameters introducing correlation between inter-arrival and service times, according to some trace of inter-arrival and corresponding service times. Two different algorithms are presented. The first algorithm is based on available methods to compute a MAP from the inter-arrival times and a PH distribution from the service times. Afterward, the correlation between inter-arrival and service times is integrated by solving a quadratic programming problem over some joint moments. The second algorithm is of the expectation maximization type and computes all parameters of the MAP and the PH distribution in an iterative way. It is shown that both algorithms yield sufficiently accurate results with an acceptable effort.     

Log-Convexity of Counting Processes Evaluated at a Random end of Observation Time with Applications to Queueing Models

We consider a counting processes with independent inter-arrival times evaluated at a random end of observation time T, independent of the process. For instance, this situation can arise in a queueing model when we evaluate the number of arrivals after a random period which can depend on the process of service times. Provided that T has log-convex density, we give conditions for the inter-arrival times in the counting process so that the observed number of arrivals inherits this property. For exponential inter-arrival times (pure-birth processes) we provide necessary and sufficient conditions. As an application, we give conditions such that the stationary number of customers waiting in a queue is a log-convex random variable. We also study bounds in the approximation of log-convex discrete random variables by a geometric distribution.     

Optimal Policies for Multi-server Non-preemptive Priority Queues

We consider a multi-server non-preemptive queue with high and low priority customers, and a decision maker who decides when waiting customers may enter service. The goal is to minimize the mean waiting time for high-priority customers while keeping the queue stable. We use a linear programming approach to find and evaluate the performance of an asymptotically optimal policy in the setting of exponential service and inter-arrival times.     

Models and Approximations for Call Center Design

A call center is a facility for delivering telephone service, both incoming and outgoing. This paper addresses optimal staffing of call centers, modeled as M/G/n queues whose offered traffic consists of multiple customer streams, each with an individual priority, arrival rate, service distribution and grade of service (GoS) stated in terms of equilibrium tail waiting time probabilities or mean waiting times. The paper proposes a methodology for deriving the approximate minimal number of servers that suffices to guarantee the prescribed GoS of all customer streams. The methodology is based on an analytic approximation, called the Scaling-Erlang (SE) approximation, which maps the M/G/n queue to an approximating, suitably scaled M/G/1 queue, for which waiting time statistics are available via the Pollaczek-Khintchine formula in terms of Laplace transforms. The SE approximation is then generalized to M/G/n queues with multiple types of customers and non-preemptive priorities, yielding the Priority Scaling-Erlang (PSE) approximation. A simple goal-seeking search, utilizing SE/PSE approximations, is presented for the optimal staffing level, subject to GoS constraints. The efficacy of the methodology is demonstrated by comparing the number of servers estimated via the PSE approximation to their counterparts obtained by simulation. A number of case studies confirm that the SE/PSE approximations yield optimal staffing results in excellent agreement with simulation, but at a fraction of simulation time and space.     

A tollbooth tandem queue with heterogeneous servers

We study a tandem queueing system with K servers and no waiting space in between. A customer needs service from one server but can leave the system only if all down-stream servers are unoccupied. Such a system is often observed in toll collection during rush hours in transportation networks, and we call it a tollbooth tandem queue. We apply matrix-analytic methods to study this queueing system, and obtain explicit results for various performance measures. Using these results, we can efficiently compute the mean and variance of the queue lengths, waiting time, sojourn time, and departure delays. Numerical examples are presented to gain insights into the performance and design of the tollbooth tandem queue. In particular, it reveals that the intuitive result of arranging servers in decreasing order of service speed (i.e., arrange faster servers at downstream stations) is not always optimal for minimizing the mean queue length or mean waiting time.     

A tandem GI/PH/1→•/PH/1/0 queue with blocking

Tandem queues are widely used in mathematical modeling of random processes describing the operation of manufacturing systems, supply chains, computer and telecommunication networks. Although there exists a lot of publications on tandem queueing systems, analytical research on tandem queues with non-Markovian input is very limited. In this paper, the results of analytical investigation of two-node tandem queue with arbitrary distribution of inter-arrival times are presented. The first station of the tandem is represented by a single-server queue with infinite waiting room. After service at the first station, a customer proceeds to the second station that is described by a single-server queue without a buffer. Service times of a customer at the first and the second server have PH (Phase-type) distributions. A customer, who completes service at the first server and meets a busy second server, is forced to wait at the first server until the second server becomes available. During the waiting period, the first server becomes blocked, i.e., not available for service of customers. We calculate the joint stationary distribution of the system states at the embedded epochs and at arbitrary time. The Laplace–Stieltjes transform of the sojourn time distribution is derived. Key performance measures are calculated and numerical results presented.     

A BMAP/SM/1 queue with service times depending on the arrival process

We study a BMAP/>SM/1 queue with batch Markov arrival process input and semi‐Markov service. Service times may depend on arrival phase states, that is, there are many types of arrivals which have different service time distributions. The service process is a heterogeneous Markov renewal process, and so our model necessarily includes known models. At first, we consider the first passage time from level {κ+1} (the set of the states that the number of customers in the system is κ+1) to level {κ} when a batch arrival occurs at time 0 and then a customer service included in that batch simultaneously starts. The service descipline is considered as a LIFO (Last‐In First‐Out) with preemption. This discipline has the fundamental role for the analysis of the first passage time. Using this first passage time distribution, the busy period length distribution can be obtained. The busy period remains unaltered in any service disciplines if they are work‐conserving. Next, we analyze the stationary workload distribution (the stationary virtual waiting time distribution). The workload as well as the busy period remain unaltered in any service disciplines if they are work‐conserving. Based on this fact, we derive the Laplace–Stieltjes transform for the stationary distribution of the actual waiting time under a FIFO discipline. In addition, we refer to the Laplace–Stieltjes transforms for the distributions of the actual waiting times of the individual types of customers. Using the relationship between the stationary waiting time distribution and the stationary distribution of the number of customers in the system at departure epochs, we derive the generating function for the stationary joint distribution of the numbers of different types of customers at departures. This revised version was published online in June 2006 with corrections to the Cover Date.     

Further results for the M/M(a, ∞)/N batch-service system

A multi-server Markovian queueing system is considered such that an idle server will take the entire batch of waiting customers into service as soon as their number is as large as some control limit. Some new results are derived. These include the distribution of the time interval between two consecutive commencements of service (including itsrth moment) and the actual service batch size distribution. In addition, the average customer waiting time in the queue is derived by a simple combinatorial approach. This is an expanded version of “Combinatorial analysis of batch-service queues” which was presented at the ORSA/TIMS meeting, Orlando, Florida, November 1983.     

Exact waiting time and queue size distributions for equilibrium <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/1 queues with Pareto service

This paper solves the problem of finding exact formulas for the waiting time cdf and queue length distribution of first-in-first-out M/G/1 queues in equilibrium with Pareto service. The formulas derived are new and are obtained by directly inverting the relevant Pollaczek-Khinchin formula and involve single integrals of non-oscillating real valued functions along the positive real line. Tables of waiting time and queue length probabilities are provided for certain parameter values under heavy traffic conditions.      

Ergodic theorems for queuing systems with dependent inter-arrival times

We study a G/GI/1 single-server queuing model with i.i.d. service times that are independent of a stationary process of inter-arrival times. We show that the distribution of the waiting time converges to a stationary law as time tends to infinity provided that inter-arrival times satisfy a Gärtner-Ellis type condition. A convergence rate is given and a law of large numbers established. These results provide tools for the statistical analysis of such systems, transcending the standard case with independent inter-arrival times.     

On the stability of retrial queues

We consider the following Type of problems. Calls arrive at a queue of capacity K (which is called the primary queue), and attempt to get served by a single server. If upon arrival, the queue is full and the server is busy, the new arriving call moves into an infinite capacity orbit, from which it makes new attempts to reach the primary queue, until it finds it non-full (or it finds the server idle). If the queue is not full upon arrival, then the call (customer) waits in line, and will be served according to the FIFO order. If λ is the arrival rate (average number per time unit) of calls and μ is one over the expected service time in the facility, it is well known that μ > λ is not always sufficient for stability. The aim of this paper is to provide general conditions under which it is a sufficient condition. In particular, (i) we derive conditions for Harris ergodicity and obtain bounds for the rate of convergence to the steady state and large deviations results, in the case that the inter-arrival times, retrial times and service times are independent i.i.d. sequences and the retrial times are exponentially distributed; (ii) we establish conditions for strong coupling convergence to a stationary regime when either service times are general stationary ergodic (no independence assumption), and inter-arrival and retrial times are i.i.d. exponentially distributed; or when inter-arrival times are general stationary ergodic, and service and retrial times are i.i.d. exponentially distributed; (iii) we obtain conditions for the existence of uniform exponential bounds of the queue length process under some rather broad conditions on the retrial process. We finally present conditions for boundedness in distribution for the case of nonpatient (or non persistent) customers. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

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.     

Stationary tail asymptotics of a tandem queue with feedback

Motivated by applications in manufacturing systems and computer networks, in this paper, we consider a tandem queue with feedback. In this model, the i.i.d. interarrival times and the i.i.d. service times are both exponential and independent. Upon completion of a service at the second station, the customer either leaves the system with probability p or goes back, together with all customers currently waiting in the second queue, to the first queue with probability 1−p. For any fixed number of customers in one queue (either queue 1 or queue 2), using newly developed methods we study properties of the exactly geometric tail asymptotics as the number of customers in the other queue increases to infinity. We hope that this work can serve as a demonstration of how to deal with a block generating function of GI/M/1 type, and an illustration of how the boundary behaviour can affect the tail decay rate.     

Sojourn time analysis for a cyclic-service tandem queueing model with general decrementing service

A sojourn time analysis is provided for a cyclic-service tandem queue with general decrementing service which operates as follows: starting once a service of queue 1 in the first stage, a single server continues serving messages in queue 1 until either queue 1 becomes empty, or the number of messages decreases to k less than that found upon the server's last arrival at queue 1, whichever occurs first, where 1 ≤ k ≤ ∞. After service completion in queue 1, the server switches over to queue 2 in the second stage and serves all messages in queue 2 until it becomes empty. It is assumed that an arrival stream is Poissonian, message service times at each stage are generally distributed and switch-over times are zero. This paper analyzes joint queue-length distributions and message sojourn time distributions.     

Symmetric queues served in cyclic order

Consider a symmetrical system of n queues served in cyclic order by a single server. It is shown that the stationary number of customers in the system is distributed as the sum of three independent random variables, one being the stationary number of customers in a standard M/G/1 queue. This fact is used to establish an upper bound for the mean waiting time for the case where at most k customers are served at each queue per visit by the server. This approach is also used to rederive the mean waiting times for the cases of exhaustive service, gated service, and serve at most one customer at each queue per visit by the server.