A two-queue model with Bernoulli service schedule and switching times

In this paper, we present a detailed analysis of a cyclic-service queueing system consisting of two parallel queues, and a single server. The server serves the two queues with a Bernoulli service schedule described as follows. At the beginning of each visit to a queue, the server always serves a customer. At each epoch of service completion in the ith queue at which the queue is not empty, the server makes a random decision: with probability p_i, it serves the next customer; with probability 1-p_i, it switches to the other queue. The server takes switching times in its transition from one queue to the other. We derive the generating functions of the joint stationary queue-length distribution at service completion instants, by using the approach of the boundary value problem for complex variables. We also determine the Laplace-Stieltjes transforms of waiting time distributions for both queues, and obtain their mean waiting times. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the infinite server shortest queue problem: Non-symmetric case

We consider two parallel M/M/∞ queues. All servers in the first queue work at rate μ₁ and all in the second work at rate μ₂. A new arrival is routed to the system with the lesser number of customers. If both queues have equal occupancy, the arrival joins the first queue with probability ν₁, and the second with probability ν₂ = 1−ν₁. We analyze this model asymptotically. We assume that the arrival rate λ is large compared to the two service rates. We give several different asymptotic formulas, that apply for different ranges of the state space. The numerical accuracy of the asymptotic results is tested. AMS subject classification 60K25 60K30 34E20     

On the single server retrial queue with priority customers

We consider anM ₂/G ₂/1 type queueing system which serves two types of calls. In the case of blocking the first type customers can be queued whereas the second type customers must leave the service area but return after some random period of time to try their luck again. This model is a natural generalization of the classicM ₂/G ₂/1 priority queue with the head-of-theline priority discipline and the classicM/G/1 retrial queue. We carry out an extensive analysis of the system, including existence of the stationary regime, embedded Markov chain, stochastic decomposition, limit theorems under high and low rates of retrials and heavy traffic analysis.Visiting from: Department of Probability, Mechanics and Mathematics, Moscow State University, Moscow 119899, Russia.     

Analysis of a single server queue with semi-Markovian service interruption

In this paper we analyze a discrete-time single server queue where the service time equals one slot. The numbers of arrivals in each slot are assumed to be independent and identically distributed random variables. The service process is interrupted by a semi-Markov process, namely in certain states the server is available for service while the server is not available in other states. We analyze both the transient and steady-state models. We study the generating function of the joint probability of queue length, the state and the residual sojourn time of the semi-Markov process. We derive a system of Hilbert boundary value problems for the generating functions. The system of Hilbert boundary value problems is converted to a system of Fredholm integral equations. We show that the system of Fredholm integral equations has a unique solution. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the optimal control of a two-queue polling model

This paper deals with two M/M/1 queues served by a single server with threshold switching. Our main goal is to solve the Poisson equation and, as a result, give expressions for the long-run expected average cost of holding units and switching actions of the server, and the bias vector.     

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.     

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.     

A mixed priority retrial queue with negative arrivals,unreliable server and multiple vacations

A retrial queue accepting two types of positive customers and negative arrivals, mixed priorities, unreliable server and multiple vacations is considered. In case of blocking the first type customers can be queued whereas the second type customers leave the system and try their luck again after a random time period. When a first type customer arrives during the service of a second type customer, he either pushes the customer in service in orbit (preemptive) or he joins the queue waiting to be served (non-preemptive). Moreover negative arrivals eliminate the customer in service and cause server’s abnormal breakdown, while in addition normal breakdowns may also occur. In both cases the server is sent immediately for repair. When, upon a service or repair completion, the server finds no first type customers waiting in queue remains idle and activates a timer. If timer expires before an arrival of a positive customer the server departs for multiple vacations. For such a system the stability conditions and the system state probabilities are investigated both in a transient and in a steady state. A stochastic decomposition result is also presented. Interesting applications are also discussed. Numerical results are finally obtained and used to investigate system performance.     

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.     

A simple proof for the constructions of optical priority queues

Constructions of optical queues by optical Switches and fiber Delay Lines (SDL) have received a lot of attention lately. In this short paper, we provide a simple proof for the construction of a priority queue with a switch and fiber delay lines in Sarwate and Anantharam (Queueing Syst. Theory Appl. 53, 115–125, 2006). Our proof not only gives the insights needed to understand why such a construction works, but also leads to a more general result that recovers the result in Sarwate and Anantharam (Queueing Syst. Theory Appl. 53, 115–125, 2006) as a special case. This research was supported in part by the National Science Council, Taiwan, ROC, under Contract NSC-93-2213-E-007-040, Contract NSC-93-2213-E-007-095, Contract NSC-94-2213-E-007-046, and the Program for Promoting Academic Excellence of Universities NSC 94-2752-E-007-002-PAE.     

Exact emulation of a priority queue with a switch and delay lines

All-optical packet switched networking is hampered by the problem of realizing viable queues for optical packets. Packets can be buffered in delay lines, but delay lines do not functionally emulate queues from an input-output point of view. In this paper we consider the problem of exact emulation of a priority queue of size K using a switching system comprised of a switch of size (M + 1) × (M + 1), which has one distinguished input for external arrivals, one distinguished output for external departures, and fixed-length delay lines of lengths L₁, L₂, ..., L_M connecting the other inputs and outputs in pairs. We measure the complexity of such an emulation by M + 1. We prove that and present a construction which works with ; further, in our construction . We also sketch an idea for an all-optical packet switched communication network architecture based on approximate emulation of priority queues of finite size using switches and delay lines, with erasure control coding at the packet level. AMS 2000 subject classifications: Primary: 60K25; Secondary: 90B22 · 90B36 · 68R99 The work of A. D. Sarwate is supported by an NDSEG Graduate Research Fellowship which is sponsored by the U.S. Department of Defense. The work of V. Anantharam is supported by ONR grant No. N00014-1-0637, DARPA grant No. N66001-00-C-8062, and by NSF grant No. ECS 0123512.     

A preemptive repeat priority queue with resampling: Performance analysis

In this paper, we analyze a discrete-time preemptive repeat priority queue with resampling. High-priority packets have preemptive repeat priority, and interrupted low-priority packets are subjected to independent retransmission attempts. Both classes contain packets with generally distributed transmission times. We show that the use of generating functions is beneficial for analyzing the system contents and packet delay of both classes. The influence of the priority scheduling on the performance measures is illustrated by some numerical examples. This work has been supported by the Interuniversity Attraction Poles Programme–Belgian Science Policy.     

A discrete-time priority queue with two-class customers and bulk services

This paper studies the behavior of a discrete queueing system which accepts synchronized arrivals and provides synchronized services. The number of arrivals occurring at an arriving point may follow any arbitrary discrete distribution possessing finite first moment and convergent probability generating function in ¦ z ¦ 1 + with > 0. The system is equipped with an infinite buffer and one or more servers operating in synchronous mode. Service discipline may or may not be prioritized. Results such as the probability generating function of queue occupancy, average queue length, system throughput, and delay are derived in this paper. The validity of the results is also verified by computer simulations.The work reported in this paper was supported by the National Science Council of the Republic of China under Grant NSC1981-0404-E002-04.     

对一类等待空间有限的抢占优先权排队的分析

讨论M/M/1抢占优先权排队模型, 且假设低优先权顾客的等待空间有限. 该模型可以用有限位相拟生灭过程来描述. 由矩阵解析方法, 对该拟生灭过程进行了分析, 并得到排队模型平稳队长的计算公式, 最后还用数值 结果说明了方法的有效性.     

Analysis of the asymmetric shortest queue problem

In this paper we study a system consisting of two parallel servers withdifferent service rates. Jobs arrive according to a Poisson stream and generate an exponentially distributed workload. On arrival a job joins the shortest queue and in case both queues have equal lengths, he joins the first queue with probabilityq and the second one with probability 1 −q, whereq is an arbitrary number between 0 and 1. In a previous paper we showed for the symmetric problem, that is for equal service rates andq = 1/2, that the equilibrium distribution of the lengths of the two queues can be exactly represented by an infinite sum of product form solutions by using an elementary compensation procedure. The main purpose of the present paper is to prove a similar product form result for the asymmetric problem by using a generalization of the compensation procedure. Furthermore, it is shown that the product form representation leads to a numerically efficient algorithm. Essentially, the method exploits the convergence properties of the series of product forms. Because of the fast convergence an efficient method is obtained with upper and lower bounds for the exact solution. For states further away from the origin the convergence is faster. This aspect is also exploited in the paper.     

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 first passage time problem for spectrally positive Lévy processes and its application to a dynamic priority queue

We study a first passage time problem for a class of spectrally positive Lévy processes. By considering the special case where the Lévy process is a compound Poisson process with negative drift, we obtain the Laplace–Stieltjes transform of the steady-state waiting time distribution of low-priority customers in a two-class M/GI/1$M/GI/1$ queue operating under a dynamic non-preemptive priority discipline. This allows us to observe how the waiting time of customers is affected as the policy parameter varies.     

Provable bounds for the mean queue lengths in a heterogeneous priority queue

We analyze a two-class two-server system with nonpreemptive heterogeneous priority structures. We use matrix–geometric techniques to determine the stationary queue length distributions. Numerical solution of the matrix–geometric model requires that the number of phases be truncated and it is shown how this affects the accuracy of the results. We then establish and prove upper and lower bounds for the mean queue lengths under the assumption that the classes have equal mean service times. This revised version was published online in June 2006 with corrections to the Cover Date.     

Decay rate for a PH/M/2 queue with shortest queue discipline

In this paper, we consider a PH/M/2 queue in which each server has its own queue and arriving customers join the shortest queue. For this model, it has been conjectured that the decay rate of the tail probabilities for the shortest queue length in the steady state is equal to the square of the decay rate for the queue length in the corresponding PH/M/2 model with a single queue. We prove this fact in the sense that the tail probabilities are asymptotically geometric when the difference of the queue sizes and the arrival phase are fixed. Our proof is based on the matrix analytic approach pioneered by Neuts and recent results on the decay rates. AMS subject classifications: 60K25 · 60K20 · 60F10 · 90B22