Containment of socially optimal policies in multiple-facility Markovian queueing systems

We consider a Markovian queueing system with N heterogeneous service facilities, each of which has multiple servers available, linear holding costs, a fixed value of service and a first-come-first-serve queue discipline. Customers arriving in the system can be either rejected or sent to one of the N facilities. Two different types of control policies are considered, which we refer to as ‘selfishly optimal’ and ‘socially optimal’. We prove the equivalence of two different Markov Decision Process formulations, and then show that classical M/M/1 queue results from the early literature on behavioural queueing theory can be generalized to multiple dimensions in an elegant way. In particular, the state space of the continuous-time Markov process induced by a socially optimal policy is contained within that of the selfishly optimal policy. We also show that this result holds when customers are divided into an arbitrary number of heterogeneous classes, provided that the service rates remain non-discriminatory.     

Optimal Operating Policy for a Random Additional Service Facility

This paper studies the steady state behaviour of a Markovian queue wherein there is a regular service facility serving the units one by one. A search for an additional service facility for the service of a group of units is started when the queue length increases to K (0 < K < L), where L is the maximum waiting space. The search is dropped when the queue length reduces to some tolerable fixed size L - N. The availability time of an additional service facility is a random variable. The model is directed towards finding the optimal operating policy (N,K) for a queueing system with a linear cost structure.     

Heavy traffic limit for a tandem queue with identical service times

We consider a two-node tandem queueing network in which the upstream queue is M/G/1 and each job reuses its upstream service requirement when moving to the downstream queue. Both servers employ the first-in-first-out policy. We investigate the amount of work in the second queue at certain embedded arrival time points, namely when the upstream queue has just emptied. We focus on the case of infinite-variance service times and obtain a heavy traffic process limit for the embedded Markov chain.     

Analysis of Open Discrete Time Queueing Networks: A Refined Decomposition Approach

This paper deals with approximate analysis methods for open queueing networks. External and internal flows from and to the nodes are characterized by renewal processes with discrete time distributions of their interarrival times. Stationary distributions of the waiting time, the queue size and the interdeparture times are obtained using efficient discrete time algorithms for single server (GI/G/1) and multi-server (GI/D/c) nodes with deterministic service. The network analysis is extended to semi-Markovian representations of each flow among the nodes, which include parameters of the autocorrelation function.     

Two new heuristics for the <Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/<Emphasis Type="Italic">n</Emphasis>/0 queueing loss system with examples based on the two-phase Coxian distribution

In this paper, we introduce a new heuristic approach for the numerical analysis of queueing systems. In particular, we study the general, multi-server queueing loss system, the GI/G/n/0 queue, with an emphasis on the calculation of steady-state loss probabilities. Two new heuristics are developed, called the GM Heuristic and the MG Heuristic, both of which make use of an exact analysis of the corresponding single-server GI/G/1/0 queue. The GM Heuristic also uses an exact analysis of the GI/M/n/0 queue, while the MG Heuristic uses an exact analysis of the M/G/n/0 queue. Experimental results are based on the use of two-phase Coxian distributions for both the inter-arrival time and the service time; these include an error analysis for each heuristic and the derivation of experimental probability bounds for the loss probability. For the class of problems studied, it is concluded that there are likely to be many situations where the accuracy of the GM Heuristic is adequate for practical purposes. Methods are also developed for combining the GM and MG Heuristics. In some cases, this leads to approximations that are significantly more accurate than those obtained by the individual heuristics.     

A single-server queue with batch arrivals and semi-Markov services

We investigate the transient and stationary queue length distributions of a class of service systems with correlated service times. The classical \(M^X/G/1\) queue with semi-Markov service times is the most prominent example in this class and serves as a vehicle to display our results. The sequence of service times is governed by a modulating process J(t). The state of \(J(\cdot )\) at a service initiation time determines the joint distribution of the subsequent service duration and the state of \(J(\cdot )\) at the next service initiation. Several earlier works have imposed technical conditions, on the zeros of a matrix determinant arising in the analysis, that are required in the computation of the stationary queue length probabilities. The imposed conditions in several of these articles are difficult or impossible to verify. Without such assumptions, we determine both the transient and the steady-state joint distribution of the number of customers immediately after a departure and the state of the process J(t) at the start of the next service. We numerically investigate how the mean queue length is affected by variability in the number of customers that arrive during a single service time. Our main observations here are that increasing variability may reduce the mean queue length, and that the Markovian dependence of service times can lead to large queue lengths, even if the system is not in heavy traffic.     

Predicting Time-Dependent Distributions of Queues and Delays for Road Traffic at Roundabouts and Priority Junctions

Vehicle queues and delays at busy road junctions have to be treated time-dependently when the traffic demand and the available capacity are approximately equal. Existing methods allow the queue length at a given time to be directly estimated as an average over all possible evolutions of the queueing system consistent with the given initial conditions and the time-dependent arrival and service rates. The paper describes the development of methods to predict the underlying distributions. Estimates of the variance and the overall frequency distribution for queue length and delay are obtained by simulating an M/M/1 queueing model with parameters varying with time. Predictive models are developed to represent the simulation results. They require as input values of parameters describing the duration of the peak and the time-average traffic intensities and capacities.     

On the Diophantine Queueing System, <Emphasis Type="Italic">D/D</Emphasis><Superscript><Emphasis Type="Italic">a,b</Emphasis></Superscript><Emphasis Type="Italic">/</Emphasis>1

This paper considers the solution of a deterministic queueing system. In this system, the single server provides service in bulk with a threshold for the acceptance of customers into service. Analytic results are given for the steady-state probabilities of the number of customers in the system and in the queue for random and pre-arrival epochs. The solution of this system is a prerequisite to a four-point approximation to the model GI/G ^a,b /1. The paper demonstrates that the solution of such a system is not a trivial problem and can produce interesting results. The graphical solution discussed in the literature requires that the traffic intensity be a rational number. The results so generated may be misleading in practice when a control policy is imposed, even when the probability distributions for the interarrival and service times are both deterministic.     

The queue length distributions in the finite buffer bulk-service MAP/G/1 queue with multiple vacations

We consider a finite buffer batch service queueing system with multiple vacations wherein the input process is Markovian arrival process (MAP). The server leaves for a vacation as soon as the system empties and is allowed to take repeated (multiple) vacations. The service- and vacation- times are arbitrarily distributed. We obtain the queue length distributions at service completion, vacation termination, departure, arbitrary and pre-arrival epochs. Finally, some performance measures such as loss probability, average queue lengths are discussed. Computational procedure has been given when the service- and vacation- time distributions are of phase type (PH-distribution).     

The Factorization of Queueing Equations and Their Interpretation

There are many queueing systems, including the M ^x /M ^y /c queue, the GI ^x /M/c queue and the M/D/c queue, in which the distribution of the queue length at certain epochs is determined by a Markov chain with the following structure. Except for a number of boundary states, all columns of the transition matrix are identical except for a shift which assures that there is always the same element occupying the main diagonal. This paper describes how one can find the equilibrium distribution for such Markov chains. Typically, this problem is solved by factorizing of a certain expression characterizing the repeated columns. In this paper, we show that this factorization has a probabilistic significance and we use this result to develop new approaches for finding the equilibrium distribution in question.     

A queueing model for crowdsourcing

Crowdsourcing is getting popular after a number of industries such as food, consumer products, hotels, electronics, and other large retailers bought into this idea of serving customers. In this paper, we introduce a multi-server queueing model in the context of crowdsourcing. We assume that two types, say, Type 1 and Type 2, of customers arrive to a c-server queueing system. A Type 1 customer has to receive service by one of c servers while a Type 2 customer may be served by a Type 1 customer who is available to act as a server soon after getting a service or by one of c servers. We assume that a Type 1 customer will be available for serving a Type 2 customer (provided there is at least one Type 2 customer waiting in the queue at the time of the service completion of that Type 1 customer) with probability \(p, 0 \le p \le 1\). With probability \(q = 1 - p\), a Type 1 customer will opt out of serving a Type 2 customer provided there is at least one Type 2 customer waiting in the system. Upon completion of a service a free server will offer service to a Type 1 customer on an FCFS basis; however, if there are no Type 1 customers waiting in the system, the server will serve a Type 2 customer if there is one present in the queue. If a Type 1 customer decides to serve a Type 2 customer, for our analysis purposes that Type 2 customer will be removed from the system as Type 1 customer will leave the system with that Type 2 customer. Under the assumption of exponential services for both types of customers we study the model in steady state using matrix analytic methods and establish some results including explicit ones for the waiting time distributions. Some illustrative numerical examples are presented.     

Analysis of a finite MAP/G/1 queue with group services

The finite capacity queues, GI/PH/1/N and PH/G/1/N, in which customers are served in groups of varying sizes were recently introduced and studied in detail by the author. In this paper we consider a finite capacity queue in which arrivals are governed by a particular Markov renewal process, called a Markovian arrival process (MAP). With general service times and with the same type of service rule, we study this finite capacity queueing model in detail by obtaining explicit expressions for (a) the steady-state queue length densities at arrivals, at departures and at arbitrary time points, (b) the probability distributions of the busy period and the idle period of the server and (c) the Laplace-Stieltjes transform of the stationary waiting time distribution of an admitted customer at points of arrivals. Efficient algorithmic procedures for computing the steady-state queue length densities and other system performance measures when services are of phase type are discussed. An illustrative numerical example is presented.     

Analysis of <Emphasis Type="Italic">N</Emphasis>-policy queues with disastrous breakdown

In the area of optimal design and control of queues, the N-policy has received great attention. A single server queueing system with system disaster is considered where the server waits till N customers accumulate in the queue and upon the arrival of Nth customer the server begins to serve the customers until the system becomes idle or the occurrence of disaster whichever happens earlier. The system size probabilities in transient state are obtained in closed form using generating functions and steady-state system size probabilities are derived in closed form using generating functions and continued fractions. Further, the mean and variance for the number of customers in the system are derived for both transient and steady states and these results are deduced for the specific models. Time-dependent busy period distribution is also obtained. Numerical illustrations are also shown to visualize the system effect.     

On an Approximation to the Mean Response Times of Priority Classes in a Stable G/G/c/PR Queue

Analytic approximations are proposed for the mean response-times of R(≥ 2) priority classes in a stable G/G/c/PR queue with general class interarrival and service time distributions and c(≥ 2) parallel servers under pre-emptive resume (PR) scheduling. The generalized exponential (GE) distributional model is used to represent general distributions with known first two moments per class. The analysis is based on the extension of known heuristic arguments and earlier results regarding the study of the stable GE/GE/c/FCFS (c ≥ 1, single class) and GE/G/1/PR queues. Numerical examples illustrate the accuracy of the proposed approximations in relation to simulations involving different interarrival and service time distributions per class. Moreover, GE-type performance bounds on the system response time per class are defined. Comments on the role of the new mean response time expressions towards the approximation of the joint and marginal queue length distributions of a stable G/G/c/PR queue are included.     

Analysis of queues in a random environment with impatient customers

We study M/M/c queues (c = 1, 1 < c < ∞ and c = ∞) in a Markovian environment with impatient customers. The arrivals and service rates are modulated by the underlying continuous-time Markov chain. When the external environment operates in phase 2, customers become impatient. We focus our attention on the explicit expressions of the performance measures. For each case of c, the corresponding probability generating function and mean queue size are obtained. Several special cases are studied and numerical experiments are presented.     

On a Queueing System with Various Input Sources and Phase Type Service

This paper develops the steady-state behaviour of a queueing model with K-parallel input sources, finite and infinite waiting space and feedback probabilities. The steady state of the system is derived through equations governing the model in terms of the traffic intensities. Probability distribution functions for the number of units waiting for service in each queue are obtained. The mean number of units in the system is also obtained. Finally, the model is generalized to increase the number of parallel servers in the final phase. Also the number of stages of service is increased in the first phase. The model is illustrated by suitable practical applications.     

Markovian Controllable Queueing Systems with Hysteretic Policies: Busy Period and Waiting Time Analysis

We study Markovian queueing systems in which the service rate varies whenever the queue length changes. More specifically we consider controllable queues operating under the so-called hysteretic policy which provides a rather versatile class of operating rules for increasing and decreasing service rate at the arrival and service completion times. The objective of this paper is to investigate algorithmically the busy period and the waiting time distributions. Our analysis supplements the classical work of Yadin and Naor (1967) who focused on the steady-state probabilities of the system state. AMS 2000 Subject Classification 60K25, 90B22     

Stability analysis of GI/GI/c/K retrial queue with constant retrial rate

We consider a finite buffer capacity GI/GI/c/K-type retrial queueing system with constant retrial rate. The system consists of a primary queue and an orbit queue. The primary queue has \(c\) identical servers and can accommodate up to \(K\) jobs (including \(c\) jobs under service). If a newly arriving job finds the primary queue to be full, it joins the orbit queue. The original primary jobs arrive to the system according to a renewal process. The jobs have i.i.d. service times. The head of line job in the orbit queue retries to enter the primary queue after an exponentially distributed time independent of the length of the orbit queue. Telephone exchange systems, medium access protocols, optical networks with near-zero buffering and TCP short-file transfers are some telecommunication applications of the proposed queueing system. The model is also applicable in logistics. We establish sufficient stability conditions for this system. In addition to the known cases, the proposed model covers a number of new particular cases with the closed-form stability conditions. The stability conditions that we obtained have clear probabilistic interpretation.     

Optimal Control of an <Emphasis Type="Italic">M/E</Emphasis><Subscript><Emphasis Type="Italic">k</Emphasis></Subscript>/1 Queueing System with a Removable Service Station

This paper studies the optimal operation of an M/E _k /1 queueing system with a removable service station under steady-state conditions. Analytic closed-form solutions of the controllable M/E _k /1 queueing system are derived. This is a generalization of the controllable M/M/1, the ordinary M/E _k /1, and the ordinary M/M/1 queueing systems in the literature. We prove that the probability that the service station is busy in the steady-state is equal to the traffic intensity. Following the construction of the expected cost function per unit time, we determine the optimal operating policy at minimum cost.     

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.