Maximizing throughput in queueing networks with limited flexibility

We study a queueing network where customers go through several stages of processing, with the class of a customer used to indicate the stage of processing. The customers are serviced by a set of flexible servers, i.e., a server is capable of serving more than one class of customers and the sets of classes that the servers are capable of serving may overlap. We would like to choose an assignment of servers that achieves the maximal capacity of the given queueing network, where the maximal capacity is λ^∗ if the network can be stabilized for all arrival rates λ < λ^∗ and cannot possibly be stabilized for all λ > λ^∗. We examine the situation where there is a restriction on the number of servers that are able to serve a class, and reduce the maximal capacity objective to a maximum throughput allocation problem of independent interest: the total discrete capacity constrained problem (TDCCP). We prove that solving TDCCP is in general NP-complete, but we also give exact or approximation algorithms for several important special cases and discuss the implications for building limited flexibility into a system.     

A Discrete-Time Geo /G/1 Retrial Queue with General Retrial Times

We consider a discrete-time Geo/G/1 retrial queue in which the retrial time has a general distribution and the server, after each service completion, begins a process of search in order to find the following customer to be served. We study the Markov chain underlying the considered queueing system and its ergodicity condition. We find the generating function of the number of customers in the orbit and in the system. We derive the stochastic decomposition law and as an application we give bounds for the proximity between the steady-state distributions for our queueing system and its corresponding standard system. Also, we develop recursive formulae for calculating the steady-state distribution of the orbit and system sizes. Besides, we prove that the M/G/1 retrial queue with general retrial times can be approximated by our corresponding discrete-time system. Finally, we give numerical examples to illustrate the effect of the parameters on several performance characteristics.     

A disaster queue with Markovian arrivals and impatient customers

We consider a single server queueing system in which arrivals occur according to a Markovian arrival process. The system is subject to disastrous failures at which times all customers in the system are lost. Arrivals occurring during the time the system undergoes repair are stored in a buffer of finite capacity. These customers can become impatient after waiting a random amount of time and leave the system. However, these customers do not become impatient once the system becomes operable. When the system is operable, there is no limit on the number of customers who can be admitted. The structure of this queueing model is of GI/M/1-type that has been extensively studied by Neuts and others. The model is analyzed in steady state by exploiting the special nature of this type queueing model. A number of useful performance measures along with some illustrative examples are reported.     

Optimization and sensitivity analysis of controlling arrivals in the queueing system with single working vacation

This paper analyzes the F-policy M/M/1/K queueing system with working vacation and an exponential startup time. The F-policy deals with the issue of controlling arrivals to a queueing system, and the server requires a startup time before allowing customers to enter the system. For the queueing systems with working vacation, the server can still provide service to customers rather than completely stop the service during a vacation period. The matrix-analytic method is applied to develop the steady-state probabilities, and then obtain several system characteristics. We construct the expected cost function and formulate an optimization problem to find the minimum cost. The direct search method and Quasi-Newton method are implemented to determine the optimal system capacity K, the optimal threshold F and the optimal service rates (μ_B,μ_V) at the minimum cost. A sensitivity analysis is conducted to investigate the effect of changes in the system parameters on the expected cost function. Finally, numerical examples are provided for illustration purpose.     

On the longest service time in a busy period of the M⧸G⧸1 queue

This paper considers the supremum m of the service times of the customers served in a busy period of the M?G?1 queueing system. An implicit expression for the distribution m(w) of m is derived. This expression leads to some bounds for m(w), while it can also be used to obtain numerical results. The tail behaviour of m(w) is investigated, too. The results are particularly useful in the analysis of a class of tandem queueing systems.     

A semidefinite programming approach to the optimal control of a single server queueing system with imposed second moment constraints

Classical analyses of the dynamic control of multi-class queueing systems frequently yield simple priority policies as optimal. However, such policies can often result in excessive queue lengths for the low priority jobs/customers. We propose a stochastic optimisation problem in the context of a two class M/M/1 system which seeks to mitigate this through the imposition of constraints on the second moments of queue lengths. We analyse the performance of two families of parametrised heuristic policies for this problem. To evaluate these policies we develop lower bounds on the optimum cost through the achievable region approach. A numerical study points to the strength of performance of threshold policies and to directions for future research.     

On Markov?CKrein characterization of the mean waiting time in M/G/K and other queueing systems

We propose a new research direction to reinvigorate research into better understanding of the M/G/K and other queueing systems??via obtaining tight bounds on the mean waiting time as functions of the moments of the service distribution. Analogous to the classical Markov?CKrein theorem, we conjecture that the bounds on the mean waiting time are achieved by service distributions corresponding to the upper/lower principal representations of the moment sequence. We present analytical, numerical, and simulation evidence in support of our conjectures.     

A recursive method for the F-policy G/M/1/K queueing system with an exponential startup time

This paper deals with the optimal control of a finite capacity G/M/1 queueing system combined the F-policy and an exponential startup time before start allowing customers in the system. The F-policy queueing problem investigates the most common issue of controlling arrival to a queueing system. We provide a recursive method, using the supplementary variable technique and treating the supplementary variable as the remaining interarrival time, to develop the steady-state probability distribution of the number of customers in the system. We illustrate a recursive method by presenting three simple examples for exponential, 3-stage Erlang, and deterministic interarrival time distributions, respectively. A cost model is developed to determine the optimal management F-policy at minimum cost. We use an efficient Maple computer program to determine the optimal operating F-policy and some system performance measures. Sensitivity analysis is also studied.     

Assembly-like queues with finite capacity: Bounds,asymptotics and approximations

In this paper we study a queueing model of assembly-like manufacturing operations. This study was motivated by an examination of a circuit pack testing procedure in an AT & T factory. However, the model may be representative of many manufacturing assembly operations. We assume that customers fromn classes arrive according to independent Poisson processes with the same arrival rate into a single-server queueing station where the service times are exponentially distributed. The service discipline requires that service be rendered simultaneously to a group of customers consisting of exactly one member from each class. The server is idle if there are not enough customers to form a group. There is a separate waiting area for customers belonging to the same class and the size of the waiting area is the same for all classes. Customers who arrive to find the waiting area for their class full, are lost. Performance measures of interest include blocking probability, throughput, mean queue length and mean sojourn time. Since the state space for this queueing system could be large, exact answers for even reasonable values of the parameters may not be easy to obtain. We have therefore focused on two approaches. First, we find upper and lower bounds for the mean sojourn time. From these bounds we obtain the asymptotic solutions as the arrival rate (waiting room, service rate) approaches zero (infinity). Second, for moderate values of these parameters we suggest an approximate solution method. We compare the results of our approximation against simulation results and report good correspondence.     

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.     

Diffusion approximation for signaling stochastic networks

This paper introduces an unified approach to diffusion approximations of signaling networks. This is accomplished by the characterization of a broad class of networks that can be described by a set of quantities which suffer exchanges stochastically in time. We call this class stochastic Petri nets with probabilistic transitions, since it is described as a stochastic Petri net but allows a finite set of random outcomes for each transition. This extension permits effects on the network which are commonly interpreted as “routing” in queueing systems. The class is general enough to include, for instance, G-networks with negative customers and triggers as a particular case. With this class at hand, we derive a heavy traffic approximation, where the processes that drive the transitions are given by state-dependent Poisson-type processes and where the probabilities of the random outcomes are also state-dependent. The objective of this approach is to have a diffusion approximation which can be readily applied in several practical problems. We illustrate the use of the results with some numerical experiments.     

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.     

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.     

Maximum Entropy Condition in Queueing Theory

The main results in queueing theory are obtained when the queueing system is in a steady-state condition and if the requirements of a birth-and-death stochastic process are satisfied. The aim of this paper is to obtain a probabilistic model when the queueing system is in a maximum entropy condition. For applying the entropic approach, the only information required is represented by mean values (mean arrival rates, mean service rates, the mean number of customers in the system). For some one-server queueing systems, when the expected number of customers is given, the maximum entropy condition gives the same probability distribution of the possible states of the system as the birth-and-death process applied to an M/M/1 system in a steady-state condition. For other queueing systems, as M/G/1 for instance, the entropic approach gives a simple probability distribution of possible states, while no close expression for such a probability distribution is known in the general framework of a birth-and-death process.     

On a multivariate renewal-reward process involving time delays and discounting: applications to IBNR processes and infinite server queues

This paper considers a particular renewal-reward process with multivariate discounted rewards (inputs) where the arrival epochs are adjusted by adding some random delays. Then, this accumulated reward can be regarded as multivariate discounted Incurred But Not Reported claims in actuarial science and some important quantities studied in queueing theory such as the number of customers in \(G/G/\infty \) queues with correlated batch arrivals. We study the long-term behaviour of this process as well as its moments. Asymptotic expressions and bounds for quantities of interest, and also convergence for the distribution of this process after renormalization, are studied, when interarrival times and time delays are light tailed. Next, assuming exponentially distributed delays, we derive some explicit and numerically feasible expressions for the limiting joint moments. In such a case, for an infinite server queue with a renewal arrival process, we obtain limiting results on the expectation of the workload, and the covariance of queue size and workload. Finally, some queueing theoretic applications are provided.     

Approximate analysis of a gordon-newell like non-product-form queueing network

This paper is tutorial in nature. It demonstrates how a particular heuristic extension of the arrival theorem, which was introduced earlier for very special network topologies, can be effectively applied (in an essentially unchanged manner) to obtain all mean performance measures for a rich class of Gordon-Newell like non-product-form queueing networks (QNs). All nodes in the class of queueing networks discussed are either FIFO or IS (pure delay), there is a single closed chain with probabilistic routing and each FIFO node also processes customers from a dedicated open chain. The number of FIFO nodesK, the number of IS nodesL and the closed chain populationN are finite but arbitrary and closed chain customers route probabilistically according to an arbitrary routing matrixQ. The think time distribution at an IS node is general, the service time distribution for both closed chain and open chain customers at the FIFO nodes is exponential with distinct service times for each, and both IS think times and FIFO service times are node dependent.The approximation technique is enhanced by an analytic study which demonstrates that it mirrors the expected behavior of the QN in many essential respects: monotonicity, bottleneck and asymptotic behavior. Moreover, in the case of balanced QNs, the approximation yields simple and explicit expressions for all quantities of interest. The analytic study and the numerical experiments presented complement one another and suggest that this approximation technique captures the essential structure of the QN, insofar as mean performance quantities are concerned.Currently on leave of absence from Bell Laboratories, at The Chinese University of Hong Kong, Department of Information Engineering, New Territories, Hong Kong.     

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.     

Dynamic admission and service rate control of a queue

This paper investigates a queueing system in which the controller can perform admission and service rate control. In particular, we examine a single-server queueing system with Poisson arrivals and exponentially distributed services with adjustable rates. At each decision epoch the controller may adjust the service rate. Also, the controller can reject incoming customers as they arrive. The objective is to minimize long-run average costs which include: a holding cost, which is a non-decreasing function of the number of jobs in the system; a service rate cost c(x), representing the cost per unit time for servicing jobs at rate x; and a rejection cost κ for rejecting a single job. From basic principles, we derive a simple, efficient algorithm for computing the optimal policy. Our algorithm also provides an easily computable bound on the optimality gap at every step. Finally, we demonstrate that, in the class of stationary policies, deterministic stationary policies are optimal for this problem.     

G-networks with multiple classes of signals and positive customers

G-networks are queueing models in which the types of customers one usually deals with in queues are enriched in several ways. In Gnetworks, positive customers are those that are ordinarily found in queueing systems; they queue up and wait for service, obtain service and then leave or go to some other queue. Negative customers have the specific function of destroying ordinary or positive customers. Finally triggers simply move an ordinary customer from one queue to the other. The term “signal” is used to cover negative customers and triggers. G-networks contain these three type of entities with certain restrictions; positive customers can move from one queue to another, and they can change into negative customers or into triggers when they leave a queue. On the other hand, signals (i.e. negative customers and triggers) do not queue up for service and simply disappear after having joined a queue and having destroyed or moved a negative customer. This paper considers this class of networks with multiple classes of positive customers and of signals. We show that with appropriate assumptions on service times, service disciplines, and triggering or destruction rules on the part of signals, these networks have a product form solution, extending earlier results.