Exponential bounds for queues with Markovian arrivals

Exponential bounds [queueb]e ^b are found for queues whose increments are described by Markov Additive Processes. This is done by application of maximal inequalities to exponential martingales for such processes. Through a thermodynamic approach the constant is shown to be the decay rate for an asymptotic lower bound for the queue length distribution. The class of arrival processes considered includes a wide variety of Markovian multiplexer models, and a general treatment of these is given, along with that of Markov modulated arrivals. Particular attention is paid to the calculation of the prefactor .     

Transient analysis of queues with heterogeneous arrivals

In this paper we consider a discrete time queueing model where the time axis is divided into time slots of unit length. The model satisfies the following assumptions: (i) an event is either an arrival of typei of batch sizeb _i, i=1,...,r with probability _i or is a depature of a single customer with probability or zero depending on whether the queue is busy or empty; (ii) no more than one event can occur in a slot, therefore the probability that neither an arrival nor a departure occurs in a slot is 1––_{i i} or 1–_{i i} according as the queue is busy or empty; (iii) events in different slots are independent. Using a lattice path representation in higher dimensional space we will derive the time dependent joint distribution of the number of arrivals of various types and the number of completed services. The distribution for the corresponding continuous time model is found by using weak convergence.     

Discrete time queues with delayed information

We study the behavior of a single-server discrete-time queue with batch arrivals, where the information on the queue length and possibly on service completions is delayed. Such a model describes situations arising in high speed telecommunication systems, where information arrives in messages, each comprising a variable number of fixed-length packets, and it takes one unit of time (a slot) to transmit a packet. Since it is not desirable to attempt service when the system may be empty, we study a model where we assume that service is attempted only if, given the information available to the server, it is certain that there are messages in the queue. We characterize the probability distribution of the number of messages in the queue under some general stationarity assumptions on the arrival process, when information on the queue size is delayedK slots, and derive explicit expressions of the PGF of the queue length for the case of i.i.d. batch arrivals and general independent service times. We further derive the PGF of the queue size when information onboth the queue length and service completion is delayedK=1 units of time. Finally, we extend the results to priority queues and show that when all messages are of unit length, thec rule remains optimal even in the case of delayed information.     

Product form in networks of queues with batch arrivals and batch services

A product form equilibrium distribution is derived for a class of queueing networks in either discrete or continuous time, in which multiple customers arrive simultaneously and batches of customers complete service simultaneously.     

Two queues with non-stochastic arrivals

This article presents a paradigm where no stochastic assumptions are made on a queue’s arrival process. To this end, we study two queueing systems which exhibit a form of stability under an arbitrary arrival process. The first queueing system applies Blackwell’s Approachability Theorem and the second analyzes the Vacuum Cleaner Problem.     

Synchronized queues with deterministic arrivals

We consider m independent exponential servers in parallel, driven by the same deterministic input. This is a modification of the Flatto-Hahn-Wright model which turns out to be easily tractable. We focus on the time-stationary distribution of the number of customers which is obtained using the Palm inversion formula.     

Simple bounds and monotonicity results for finite multi-server exponential tandem queues

Simple and computationally attractive lower and upper bounds are presented for the call congestion such as those representing multi-server loss or delay stations. Numerical computations indicate a potential usefulness of the bounds for quick engineering purposes. The bounds correspond to product-form modifications and are intuitively appealing. A formal proof of the bounds and related monotonicity results will be presented. The technique of this proof, which is based on Markov reward theory, is of interest in itself and seems promising for further application. The extension to the non-exponential case is discussed. For multiserver loss stations the bounds are argued to be insensitive.     

Single-server queues with spatially distributed arrivals

Consider a queueing system where customers arrive at a circle according to a homogeneous Poisson process. After choosing their positions on the circle, according to a uniform distribution, they wait for a single server who travels on the circle. The server's movement is modelled by a Brownian motion with drift. Whenever the server encounters a customer, he stops and serves this customer. The service times are independent, but arbitrarily distributed. The model generalizes the continuous cyclic polling system (the diffusion coefficient of the Brownian motion is zero in this case) and can be interpreted as a continuous version of a Markov polling system. Using Tweedie's lemma for positive recurrence of Markov chains with general state space, we show that the system is stable if and only if the traffic intensity is less than one. Moreover, we derive a stochastic decomposition result which leads to equilibrium equations for the stationary configuration of customers on the circle. Steady-state performance characteristics are determined, in particular the expected number of customers in the system as seen by a travelling server and at an arbitrary point in time.     

The marshall and stoyan bounds for IMRL/G/1 queues are tight

Previously established upper and lower bounds for the mean waiting time in a GI/G/1 queue given an interarrival-time distribution with increasing mean residual life are shown to be tight. Distributions for which the inequalities become equalities are displayed. The corresponding bounds for DMRL distributions are not tight.     

Optimal admission policies for a finite queue with bursty arrivals

We consider a service system with a single server, a finite waiting room and two classes of customers with deterministic service time. Primary jobs arrive at random and are admitted whenever there is room in the system. At the beginning of each period, secondary jobs can be admitted from an infinite pool. A revenue is earned upon admission of each job, with the primary jobs bringing a higher contribution than the secondary jobs, the objective being to maximize the total discounted revenue over an infinite horizon. We model the system as a discrete time Markov decision process and show that a monotone admission policy is optimal when the number of primary arrivals has a fixed distribution. Moreover, when the primary arrival distribution varies with time according to a finite state Markov chain, we show that the optimal policy is conditionally monotone and that the numerical computation of an optimal policy, in this case, is substantially more difficult than in the case of stationary arrivals.This research was supported in part by the National Science Foundation, under grant ECS-8803061, while the author was at the University of Arizona.     

New bounds for expected delay in FIFO M/G/c queues

Most bounds for expected delay, E[D], in GI/GI/c queues are modifications of bounds for the GI/GI/1 case. In this paper we exploit a new delay recursion for the GI/GI/c queue to produce bounds of a different sort when the traffic intensity p = λ/μ = E[S]/E[T] is less than the integer portion of the number of servers divided by two. (S AND T denote generic service and interarrival times, respectively.) We derive two different families of new bounds for expected delay, both in terms of moments of S AND T. Our first bound is applicable when E[S₂] < ∞. Our second bound for the first time does not require finite variance of S; it only involves terms of the form E[S^β], where 1 < β < 2. We conclude by comparing our bounds to the best known bound of this type, as well as values obtained from simulation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Some results for the queues Mx/M/c and GIx/ G/c

We develop for the queue M^x/M/c an upper bound for the mean queue length and lower bounds for the delay probabilities (that of an arrival group and that of an arbitrary customer in the arrival group). An approximate formula is also developed for the general bulk-arrival queue GI^x/G/c. Preliminary numerical studies have indicated excellent performance of the results.     

Improved lower bounds for the capacitated lot sizing problem with setup times

We present new lower bounds for the capacitated lot sizing problem, applying decomposition to the network reformulation. The demand constraints are the linking constraints and the problem decomposes into subproblems per period containing the capacity and setup constraints. Computational results and a comparison to other lower bounds are presented.     

Queues with group arrivals and exhaustive service discipline

Queues with compound Poisson arrivals, phase-type service and exhaustive service discipline are studied. An algorithmic method is developed to compute the steady-state probability distribution of the number of customers in the system with unlimited or limited queue capacities. Examples with different model parameters are given to show the computational efficiency of the method. In the Appendix, the stochastic decomposition property for the queues with single arrivals and with exhaustive service discipline is extended to queues with group arrivals.     

Improved bounds for minimal feedback vertex sets in tournaments

We study feedback vertex sets (FVS) in tournaments, which are orientations of complete graphs. As our main result, we show that any tournament on n nodes has at most 1.5949ⁿ minimal FVS. This significantly improves the previously best upper bound of 1.6667ⁿ by Fomin et al. [STOC 2016] and 1.6740ⁿ by Gaspers and Mnich [J. Graph Theory 72 (1):72–89, 2013]. Our new upper bound almost matches the best‐known lower bound of , due to Gaspers and Mnich. Our proof is algorithmic, and shows that all minimal FVS of tournaments can be enumerated in time .     

Batch arrival queues with vacations and server setup

We study a single server queueing system whose arrival stream is compound Poisson and service times are generally distributed. Three types of idle period are considered: threshold, multiple vacations, and single vacation. For each model, we assume after the idle period, the server needs a random amount of setup time before serving. We obtain the steady-state distributions of system size and waiting time and expected values of the cycle for each model. We also show that the distributions of system size and waiting time of each model are decomposed into two parts, whose interpretations are provided. As for the threshold model, we propose a method to find the optimal value of threshold to minimize the total expected operating cost.     

Algorithmic methods for multi-server queues with group arrivals and exponential services

We discuss algorithms for the computation of the steady-state features of the c-server queue with exponential service times and bounded group arrivals. While our methods are valid for general interarrival time distributions, we treat in detail the simplifications obtained by using a distribution of phase type. Oueue length densities at times prior to arrivals and at arbitrary times are obtained in a modified matrix-geometric form. Their means and variances are found in computationally tractable forms. We also present algorithmic methods for the waiting time and the virtual waiting time distributions of a customer in a group and obtain the means and variances of these distributions in tractable forms. Numerical examples show that the effects of changing various parameters of the queuing model may so be examined at a small computational cost.