Analysis of an open tandem queueing network with population constraint and constant service times 1

We consider an open tandem queueing network with population constraint and constant service times. The total number of customers that may be present in the network can not exceed a given value K. Customers arriving at the queueing network when there are more than K customers are forced to wait in an external queue. The arrival process to the queueing network is assumed to be arbitrary. We show that this queueing network can be transformed into a simple network involving only two nodes. Using this simple network, we obtain an upper and lower bound on the mean waiting time. These bounds can be easily calculated. Validations against simulation data establish the tightness of these bounds.     

Waiting time distributions in the accumulating priority queue

We are interested in queues in which customers of different classes arrive to a service facility, and where performance targets are specified for each class. The manager of such a queue has the task of implementing a queueing discipline that results in the performance targets for all classes being met simultaneously. For the case where the performance targets are specified in terms of ratios of mean waiting times, as long ago as the 1960s, Kleinrock suggested a queueing discipline to ensure that the targets are achieved. He proposed that customers accumulate priority as a linear function of their time in the queue: the higher the urgency of the customer’s class, the greater the rate at which that customer accumulates priority. When the server becomes free, the customer (if any) with the highest accumulated priority at that time point is the one that is selected for service. Kleinrock called such a queue a time-dependent priority queue, but we shall refer to it as the accumulating priority queue. Recognising that the performance of many queues, particularly in the healthcare and human services sectors, is specified in terms of tails of waiting time distributions for customers of different classes, we revisit the accumulating priority queue to derive its waiting time distributions, rather than just the mean waiting times. We believe that some elements of our analysis, particularly the process that we call the maximum priority process, are of mathematical interest in their own right.     

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.     

Last in line

Queueing is a common praxis in banks, hospitals and transportation, just to name a few. One common performance metric is the mean sojourn time. However, humans experience waiting time in a more complex manner — they dislike being the last in line. We study queueing systems subject to such a cost structure. For the single M/G/1 queue, we derive the corresponding mean costs, value functions and admission costs, which are then applied to route customers to parallel servers.     

An M/G/1 Queueing Model with Gated Random Order of Service

We analyse an M/G/1 queueing model with gated random order of service. In this service discipline there are a waiting room, in which arriving customers are collected, and a service queue. Each time the service queue becomes empty, all customers in the waiting room are put instantaneously and in random order into the service queue. The service times of customers are generally distributed with finite mean. We derive various bivariate steady-state probabilities and the bivariate Laplace–Stieltjes transform (LST) of the joint distribution of the sojourn times in the waiting room and the service queue. The derivation follows the line of reasoning of Avi-Itzhak and Halfin [4]. As a by-product, we obtain the joint sojourn times LST for several other gated service disciplines.     

Jitter analysis of an MMPP-2 tagged stream in the presence of an MMPP-2 background stream

We first consider a single-server queue that serves a tagged MMPP-2 stream and a background MMPP-2 stream in a FIFO manner. The service time is exponentially distributed. For this queueing system, we obtain the CDF of the tagged inter-departure time, from which we can calculate the jitter, defined as a percentile of the inter-departure time. The formulation is exact, but the solution is obtained numerically, which introduces an error that has been found to be negligible. Subsequently, we consider a tandem queueing network consisting of N tandem queues, which is traversed by the MMPP-2 tagged stream, and where each queue also serves a local MMPP-2 background stream. For this queueing network, we obtain an upper bound on the CDF of the inter-departure time from the Nth queue using a heavy traffic approximation, and we verify it by simulation.     

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.     

Some notes on the reduction of network dimensionality in nested open queueing networks

In this paper, we study an open and nested tandem queueing network, where the population constraint within each subnetwork is controlled by a semaphore queue. The total number of customers that may be present in the subnetwork can not exceed a given value. Each node has a constant service time and the arrival process to the queueing network follows an arbitrary distribution.A major characteristic of this queueing network is that the low layer flow is halted by the state of the high layer. We develop a simple and equivalent queueing network that has the same performance characteristics as the original queueing network. Using this model, the waiting time on the queueing network can be easily derived. It is interesting to see how the simplification process can be applied to multi-layered queueing network.     

Stationary Distributions of GI/M/c Queue with PH Type Vacations

We study a GI/M/c type queueing system with vacations in which all servers take vacations together when the system becomes empty. These servers keep taking synchronous vacations until they find waiting customers in the system at a vacation completion instant.The vacation time is a phase-type (PH) distributed random variable. Using embedded Markov chain modeling and the matrix geometric solution methods, we obtain explicit expressions for the stationary probability distributions of the queue length at arrivals and the waiting time. To compare the vacation model with the classical GI/M/c queue without vacations, we prove conditional stochastic decomposition properties for the queue length and the waiting time when all servers are busy. Our model is a generalization of several previous studies.     

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.     

The infinite-buffer single server queue with a variant of multiple vacation policy and batch Markovian arrival process

We consider an infinite-buffer single server queue where arrivals occur according to a batch Markovian arrival process (BMAP). The server serves until system emptied and after that server takes a vacation. The server will take a maximum number H of vacations until either he finds at least one customer in the queue or the server has exhaustively taken all the vacations. We obtain queue length distributions at various epochs such as, service completion/vacation termination, pre-arrival, arbitrary, departure, etc. Some important performance measures, like mean queue lengths and mean waiting times, etc. have been obtained. Several other vacation queueing models like, single and multiple vacation model, queues with exceptional first vacation time, etc. can be considered as special cases of our model.     

The state-dependent <Emphasis Type="Italic">M</Emphasis> / <Emphasis Type="Italic">G</Emphasis> / 1 queue with orbit

We consider a state-dependent single-server queue with orbit. This is a versatile model for the study of service systems, where the server needs a non-negligible time to retrieve waiting customers every time he completes a service. This situation arises typically when the customers are not physically present at a system, but they have a remote access to it, as in a call center station, a communication node, etc. We introduce a probabilistic approach for the performance evaluation of this queueing system, that we refer to as the queueing and Markov chain decomposition approach. Moreover, we discuss the applicability of this approach for the performance evaluation of other non-Markovian service systems with state dependencies.     

Two Queues with Weighted One-Way Overflow

We consider an open queueing network consisting of two queues with Poisson arrivals and exponential service times and having some overflow capability from the first to the second queue. Each queue is equipped with a finite number of servers and a waiting room with finite or infinite capacity. Arriving customers may be blocked at one of the queues depending on whether all servers and/or waiting positions are occupied. Blocked customers from the first queue can overflow to the second queue according to specific overflow routines. Using a separation method for the balance equations of the two-dimensional server and waiting room demand process, we reduce the dimension of the problem of solving these balance equations substantially. We extend the existing results in the literature in three directions. Firstly, we allow different service rates at the two queues. Secondly, the overflow stream is weighted with a parameter p ∈ [0,1], i.e., an arriving customer who is blocked and overflows, joins the overflow queue with probability p and leaves the system with probability 1 − p. Thirdly, we consider several new blocking and overflow routines. An erratum to this article can be found at     

On the asymptotic optimality of the cμ-rule in queueing networks

Although the cμ-rule is proven to be exactly or asymptotically optimal in various parallel queueing networks, its performance in non-parallel queueing networks is relatively unexplored. We study the performance of the cμ-rule (that is, the performance of implementing the cμ-rule at all servers) in non-parallel queueing networks. We numerically show that the cμ-rule can perform poorly even in a simple tandem queue with two job types. We derive conditions under which the cμ-rule is asymptotically optimal in diffusion scale.     

System delay versus system content for discrete-time queueing systems subject to server interruptions

This paper concerns discrete-time queueing systems operating under a first-come-first-served queueing discipline, with deterministic service times of one slot and subject to independent server interruptions. For such systems, we derive a relationship between the probability generating functions of the system content during an arbitrary slot and of the system delay of an arbitrary customer. This relationship is valid regardless of the nature of the arrival process. From this relationship we derive a relationship between the first- and second-order moments of the distributions involved. It is shown that the relationship also applies to subsystems of the queueing system being discussed, and to the waiting time and queue content of a multi-server queueing system with geometric service times and uninterrupted servers.     

Analysis of an SPP/G/1 system with multiple vacations and E-limited service discipline

Many researchers have studied variants of queueing systems with vacations. Most of them have dealt with M/G/1 systems and have explicitly analyzed some of their performance measures, such as queue length, waiting time, and so on. Recently, studies on queueing systems whose arrival processes are not Poissonian have appeared. We consider a single server queueing system with multiple vacations and E-limited service discipline, where messages arrive to the system according to a switched Poisson process. First, we consider the joint probability density functions of the queue length and the elapsed service time or the elapsed vacation time. We derive the equations for these pdf's, which include a finite number of unknown values. Using Rouché's theorem, we determine the values from boundary conditions. Finally, we derive the transform of the stationary queue length distribution explicitly.     

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.     

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.     

On the Three Threshold Policy in the Multi-Server Queueing System with Vacations

In this paper, we study an M/M/c queue with a three threshold vacation policy denoted by (e, d, N). With such a policy, the servers keep serving the customers until the number of idle servers reaches d and then e of d servers start taking a vacation together. These e servers keep taking vacations until the number of customers in the system is at least N at a vacation completion instant, then the e servers return to serve the queue again. Using the matrix analytic method, we obtain the stationary performance measures and prove the conditional stochastic decomposition properties for the waiting time and queue length. This model is a generalization of previous multi-server vacation models and offers a useful performance evaluation and system design tool in multi-task server queueing systems.     

Non-stationary waiting times in a closed exponential tandem queue

A closed exponential tandem queue in which every customer has to be served by two servers is considered. Given the numbers of customers lined up at each of the two servers, we derive the probability distributions of the waiting time of any customer until his second service is completed, and of the total busy time of the system.