An analytical solution for a tandem queue with blocking

The model considered in this paper involves a tandem queue with two waiting lines, and as soon as the second waiting line reaches a certain upper limit, the first line is blocked. Both lines have exponential servers, and arrivals are Poisson. The objective is to determine the joint distribution of both lines in equilibrium. This joint distribution is found by using generalized eigenvalues. Specifically, a simple formula involving the cotangent is derived. The periodicity of the cotangent is then used to determine the location of the majority of the eigenvalues. Once all eigenvalues are found, the eigenvectors can be obtained recursively. The method proposed has a lower computational complexity than all other known methods. This revised version was published online in June 2006 with corrections to the Cover Date.     

Admission control and pricing in a queue with batch arrivals

We investigate a problem of admission control in a queue with batch arrivals. We consider a single server with exponential service times and a compound Poisson arrival process. Each arriving batch computes its expected benefit and decides whether or not to enter the system. The controller’s problem is to set state dependent prices for arriving batches. Once prices have been set we formulate the admission control problem, derive properties of the value function, and obtain the optimal admission policy.     

A retrial queue with redundancy and unreliable server

Retrial queues are useful in the stochastic modelling of computer and telecommunication systems amongst others. In this paper we study a version of the retrial queue with variable service. Such a point of view gives another look at the unreliable retrial queueing problem which includes the redundancy model.By using the theory of piecewise Markovian processes, we obtain the analogue of the Pollaczek-Khintchine formula for such retrial queues, which is useful for operations researchers to obtain performance measures of interest.     

A decomposition-related throughput property of tandem queueing networks with blocking

A general throughput property of tandem queueing networks with blocking that relates existing decomposition methods to throughput bounds is discussed using the sample path approach.     

Maximizing throughput in finite-source parallel queue systems

Motivated by the dispatching of trucks to shovels in surface mines, we study optimal routing in a Markovian finite-source, multi-server queueing system with heterogeneous servers, each with a separate queue. We formulate the problem of routing customers to servers to maximize the system throughput as a Markov Decision Process. When the servers are homogeneous, we demonstrate that the Shortest Queue policy is optimal, and when the servers are heterogeneous, we partially characterize the optimal policy and present a near-optimal and simple-to-implement policy. We use the model to illustrate the substantial benefits of pooling, by comparing it to the permanent assignment of customers to servers.     

Managing marketing information: Nigel Piercy and Martin Evans Croom Helm,London, 1983, 223 pages

This note reports in a unified way some analytic results on the queuing system GI^X/M/1. It also corrects some erroneous results reported by Jensen and Paulson, and Krakowski.     

Optimal order of servers in a tandem queue with general blocking

In this paper, using the bivariate characterizations of thereversed hazard rate ordering and thestochastic ordering, and thepairwise interchange argument, we characterize the best strategy for allocating servers in a tandem system controlled using thegeneral blocking or theproduction authorization card (PAC) schemes. We show that when there is no buffer space between the first (resp. the last) two servers, it is better to allocate the slower server to the first (resp. the last) stage. The result extends previous results to systems where the number of buffers at the interior stages may be greater than one and the blocking mechanism may be more general. In particular, our results apply to manufacturing blocking, kanban blocking, a variation of kanban blocking, and the integral control scheme previously studied in the literature.     

A two-stage tandem queue attended by a moving server with holding and switching costs

We consider a two-stage tandem queue attended by a moving server, with homogeneous Poisson arrivals and general service times. Two different holding costs for stages 1 and 2 and different switching costs from one stage to the other are considered. We show that the optimal policy in the second stage is greedy; and if the holding cost rate in the second stage is greater or equal to the rate in the first stage, then the optimal policy in the second stage is also exhaustive. Then, the optimality condition for sequential service policy in systems with zero switchover times is introduced. Considering some properties of the optimal policy, we then define a Triple-Threshold (TT) policy to approximate the optimal policy in the first stage. Finally, a model is introduced to find the optimal TT policy, and using numerical results, it is shown that the TT policy accurately approximates the optimal policy. This revised version was published online in June 2006 with corrections to the Cover Date.     

The customer response times in the processor sharing queue are associated

The customer response times in the egalitarian processor sharing queue are shown to be associated random variables under renewal inputs and general independent service times assumptions.The work by this author was supported in part by the National Science Foundation under grant ASC 88-8802764 and by the Office of Naval Research under grant ONR N00014-87-K-0796.     

A Discrete-Time Geo/G/1 retrial queue with the server subject to starting failures

This paper studies a discrete-time Geo/G/1 retrial queue where the server is subject to starting failures. We analyse the Markov chain underlying the regarded queueing system and present some performance measures of the system in steady-state. Then, we give two stochastic decomposition laws and find a measure of the proximity between the system size distributions of our model and the corresponding model without retrials. We also develop a procedure for calculating the distributions of the orbit and system size as well as the marginal distributions of the orbit size when the server is idle, busy or down. Besides, we prove that the M/G/1 retrial queue with starting failures can be approximated by its discrete-time counterpart. Finally, some numerical examples show the influence of the parameters on several performance characteristics. This work is supported by the DGINV through the project BFM2002-02189.     

On the transient behavior of the processor sharing queue

We analyze the transient behavior of the single server queue under the processor sharing discipline. Under fairly general assumptions, we give the rate of growth of the number of customers in the queue as well as the asymptotic behavior of the residual service times described in terms of a renormalized point process.     

Approximation of throughput in tandem queues with multiple servers and blocking

In this paper, we develop an approximation method for throughput in tandem queues with multiple independent reliable servers at each stage and finite buffers between service stations. We consider the blocking after service (BAS) blocking protocol of each service stage. The service time distribution of each server is exponential. The approximation is based on the decomposition of the system into a set of coupled subsystems which are modeled by two-stage tandem queue with two buffers and are analyzed by using the level dependent quasi-birth-and-death (LDQBD) process.     

Generalized parallel-server fork-join queues with dynamic task scheduling

This paper introduces a generalization of the classical parallel-server fork-join queueing system in which arriving customers fork into multiple tasks, every task is uniquely assigned to one of the set of single-server queues, and each task consists of multiple iterations of different stages of execution, including task vacations and communication among sibling tasks. Several classes of dynamic polices are considered for scheduling multiple tasks at each of the single-server queues to maintain effective server utilization. The paper presents an exact matrix-analytic analysis of generalized parallel-server fork-join queueing systems, for small instances of the stochastic model, and presents an approximate matrix-analytic analysis and fixed-point solution, for larger instances of the model.     

A tandem of discrete-time queues with arrivals and departures at each stage

A discrete-time system of a tandem of queues with exogenous arrivals and departures at each stage is considered. A customer leaving queuek–1 departs the system with probability 1– ^[k] and continues to queuek with probability ^[k] . Exogenous arrivals to each stage are i.i.d. at each time slot. An approximate analysis of the occupancy and busy-period distributions of each stage based on a General Busy-period with batches and Memoryless (geometric) Idle period renewal Process (GBMIP) provides improved performance over two-state Markov approximations and gives exact results when there are no interstage departures.This research was supported in part by NSF grant NCR-8708282.     

Optimal server assignment in a two-stage tandem queueing system

We study Markovian queueing systems consisting of two stations in tandem. There is a dedicated server in each station and an additional server that can be assigned to any station. Assuming that linear holding costs are incurred by jobs in the system and two servers can collaborate to work on the same job, we determine structural properties of optimal server assignment policies under the discounted and the average cost criteria.     

Optimality of a Threshold Policy in theM/M/ queue with repeated vacations

Consider anM/M/1 queueing system with server vacations where the server is turned off as soon as the queue gets empty. We assume that the vacation durations form a sequence of i.i.d. random variables with exponential distribution. At the end of a vacation period, the server may either be turned on if the queue is non empty or take another vacation. The following costs are incurred: a holding cost ofh per unit of time and per customer in the system and a fixed cost of each time the server is turned on. We show that there exists a threshold policy that minimizes the long-run average cost criterion. The approach we use was first proposed in Blanc et al. (1990) and enables us to determine explicitly the optimal threshold and the optimal long-run average cost in terms of the model parameters.     

A single server queue with service interruptions

In this paper we characterize the queue-length distribution as well as the waiting time distribution of a single-server queue which is subject to service interruptions. Such queues arise naturally in computer and communication problems in which customers belong to different classes and share a common server under some complicated service discipline. In such queues, the viewpoint of a given class of customers is that the server is not available for providing service some of the time, because it is busy serving customers from a different class. A natural special case of these queues is the class of preemptive priority queues. In this paper, we consider arrivals according the Markovian Arrival Process (MAP) and the server is not available for service at certain times. The service times are assumed to have a general distribution. We provide numerical examples to show that our methods are computationally feasible. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the steady-state queue size distribution of the discrete-timeGeo/G/1 queue with repeated customers

In this paper, we study the steady-state queue size distribution of the discrete-timeGeo/G/1 retrial queue. We derive analytic formulas for the probability generating function of the number of customers in the system in steady-state. It is shown that the stochastic decomposition law holds for theGeo/G/1 retrial queue. Recursive formulas for the steady-state probabilities are developed. Computations based on these recursive formulas are numerically stable because the recursions involve only nonnegative terms. Since the regularGeo/G/1 queue is a special case of theGeo/G/1 retrial queue, the recursive formulas can also be used to compute the steady-state queue size distribution of the regularGeo/G/1 queue. Furthermore, it is shown that a continuous-timeM/G/1 retrial queue can be approximated by a discrete-timeGeo/G/1 retrial queue by dividing the time into small intervals of equal length and the approximation approaches the exact when the length of the interval tends to zero. This relationship allows us to apply the recursive formulas derived in this paper to compute the approximate steady-state queue size distribution of the continuous-timeM/G/1 retrial queue and the regularM/G/1 queue.Partially supported by the Natural Sciences and Engineering Research Council of Canada through grant OGP0046415.Partially supported by the Natural Sciences and Engineering Research Council of Canada through grant OGP0105828.     

An intermittently served discrete time queue with applications to meteor scatter communications

A discrete time single server queue with service interruptions is analyzed in the steady-state under general assumptions. The main motivation for the study is the performance evaluation of a communication protocol using ionized layers created by meteors. The analysis yields the joint distribution of the queue size and the remaining duration of the current operative or inoperative period. The solution takes a particularly simple form in the case where the operative periods have a rational generating function.On short-term visits to the University of Newcastle upon Tyne and AT&T Bell Laboratories.Work done while the author was visiting the AT&T Bell Laboratories.     

Optimal threshold policies in a two-class preemptive priority queue with admission and termination control

We consider a two-class 1 preemptive priority queue in which there are two essential, on-line decisions that have to be taken. The first is the decision to either accept or reject new type-1 or type-2 jobs. The second is the decision to abort jobs, i.e., to remove any type-1 or type-2 jobs from the system. We show that there exist optimal threshold policies for these two types of, decisions.