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.     

Discrete-time queue with Bernoulli bursty source arrival and generally distributed service times

In this contribution, a discrete-time single-server infinite-capacity queue with correlated arrivals and general service times is investigated. Arrivals of cells are modelled as an on/off source process with geometrically distributed on-periods and off-periods, which is called Bernoulli bursty source. Based on the probability generating function technique, closed-form expression of some performance measures of system, such as average buffer content, unfinished work, cell delay and so on, are obtained. Finally, the effects of system parameters on performance measures are illustrated by some numerical examples.     

Sojourn and waiting times in a single-server system with state-dependent mean service rate

A birth-death queueing system with asingle server, first-come first-served discipline, Poisson arrivals and state-dependent mean service rate is considered. The problem of determining the equilibrium densities of the sojourn and waiting times is formulated, in general. The particular case in which the mean service rate has one of two values, depending on whether or not the number of customers in the system exceeds a prescribed threshold, is then investigated. A generating function is derived for the Laplace transforms of the densities of the sojourn and waiting times, leading to explicit expressions for these quantities. Explicit expressions for the second moments of the sojourn and waiting times are also obtained.     

Relating polling models with zero and nonzero switchover times

We consider a system ofN queues served by a single server in cyclic order. Each queue has its own distinct Poisson arrival stream and its own distinct general service-time distribution (asymmetric queues), and each queue has its own distinct distribution of switchover time (the time required for the server to travel from that queue to the next). We consider two versions of this classical polling model: In the first, which we refer to as the zero-switchover-times model, it is assumed that all switchover times are zero and the server stops traveling whenever the system becomes empty. In the second, which we refer to as the nonzero-switchover-times model, it is assumed that the sum of all switchover times in a cycle is nonzero and the server does not stop traveling when the system is empty. After providing a new analysis for the zero-switchover-times model, we obtain, for a host of service disciplines, transform results that completely characterize the relationship between the waiting times in these two, operationally-different, polling models. These results can be used to derive simple relations that express (all) waiting-time moments in the nonzero-switchover-times model in terms of those in the zero-switchover-times model. Our results, therefore, generalize corresponding results for the expected waiting times obtained recently by Fuhrmann [Queueing Systems 11 (1992) 109—120] and Cooper, Niu, and Srinivasan [to appear in Oper. Res.].Research supported in part by the National Science Foundation under grant DDM-9001751.     

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.     

A note on polling models with renewal arrivals and nonzero switch-over times

We consider gated polling systems with general service and switch-over times and with renewal arrival processes. We derive closed-form expressions for the expected delay in heavy-traffic (HT). So far, proofs of HT limits have only been obtained for Poisson-type arrival processes, whereas for renewal arrivals limits are based on conjectures.     

Stationary distributions in a queueing system with vacation times and limited service

This paper deals with a modified M/G/1 queueing system with finite capacity and a walking server. Units waiting are served up to a limited number before the server takes a vacation time and later returns to the queue again. A computational method for the stationary queue length distribution is developed and illustrated with a numerical example. The model was motivated by similar channel access mechanisms in token-ring local area networks.     

Asymptotics of stochastic networks with subexponential service times

We analyse the tail behaviour of stationary response times in the class of open stochastic networks with renewal input admitting a representation as (max,+)-linear systems. For a K-station tandem network of single server queues with infinite buffer capacity, which is one of the simplest models in this class, we first show that if the tail of the service time distribution of one server, say server i ₀ ∈ {1,...,K}, is subexponential and heavier than those of the other servers, then the stationary distribution of the response time until the completion of service at server j ⩾ i ₀ asymptotically behaves like the stationary response time distribution in an isolated single-server queue with server i ₀. Similar asymptotics are given in the case when several service time distributions are subexponential and asymptotically tail-equivalent. This result is then extended to the asymptotics of general (max,+)-linear systems associated with i.i.d. driving matrices having one (or more) dominant diagonal entry in the subexponential class. In the irreducible case, the asymptotics are surprisingly simple, in comparison with results of the same kind in the Cramér case: the asymptotics only involve the excess distribution of the dominant diagonal entry, the mean value of this entry, the intensity of the arrival process, and the Lyapunov exponent of the sequence of driving matrices. In the reducible case, asymptotics of the same kind, though somewhat more complex, are also obtained. As a direct application, we give the asymptotics of stationary response times in a class of stochastic Petri nets called event graphs. This is based on the assumption that the firing times are independent and that the tail of the firing times of one of the transitions is subexponential and heavier than those of the others. An extension of these results to nonrenewal input processes is discussed. Asymptotics of queue size processes are also considered. 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.     

Scheduling in a multi-class series of queues with deterministic service times

We consider a problem of scheduling in a multi-class network of single-server queues in series, in which service times at the nodes are constant and equal. Such a model has potential application to automated manufacturing systems or packet-switched communication networks, where a message is divided into packets (or cells) of fixed lengths. The network is a series-type assembly or transfer line, with the exception that there is an additional class of jobs that requires processing only at the first node (class 0). There is a holding cost per unit time that is proportional to the total number of customers in the system. The objective is to minimize the (expected) total discounted holding cost over a finite or an infinite horizon. We show that an optimal policy gives priority to class-0 jobs at node 1 when at least one of a set ofm–1 inequalities on partial sums of the components of the state vector is satisfied. We solve the problem by two methods. The first involves formulating the problem as a (discrete-time) Markov decision process and using induction on the horizon length. The second is a sample-path approach using an interchange argument to establish optimality.The research of this author was supported by the National Science Foundation under Grant No. DDM-8719825. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.     

An M/G/1 queue with cyclic service times

In this paper we consider a single server queue with Poisson arrivals and general service distributions in which the service distributions are changed cyclically according to customer sequence number. This model extends a previous study that used cyclic exponential service times to the treatment of general service distributions. First, the stationary probability generating function and the average number of customers in the system are found. Then, a single vacation queueing system with aN-limited service policy, in which the server goes on vacation after servingN consecutive customers is analyzed as a particular case of our model. Also, to increase the flexibility of using theM/G/1 model with cyclic service times in optimization problems, an approximation approach is introduced in order to obtain the average number of customers in the system. Finally, using this approximation, the optimalN-limited service policy for a single vacation queueing system is obtained.On leave from the Department of Industrial Engineering, Iran University of Science and Technology, Narmak, Tehran 16844, Iran.     

Two-server queue with one server idle below a threshold

A birth-death queueing system with two identical servers, first-come first-served discipline, and Poisson arrivals is considered. Only one of the servers is active when the number of customers in the system does not exceed a prescribed threshold, whereas both are active above the threshold. The problem of determining the equilibrium density of the waiting time is formulated. A generating function is given for the Laplace transform of the density of the waiting time, and it is pointed out that it leads to an explicit expression for this quantity. Explicit expressions are obtained for the first and second moments of the waiting and sojourn times, and they are compared with the corresponding quantities for a single-server system with the same state-dependent mean service rates.     

A simple policy for multiple queues with size-independent service times

We consider a service system with two Poisson arrival queues. A server chooses which queue to serve at each moment. Once a queue is served, all the customers will be served within a fixed amount of time. This model is useful in studying airport shuttling or certain online computing systems. We propose a simple yet optimal state-independent policy for this problem which is not only easy to implement, but also performs very well.     

Large deviations of Markovian polling models with applications to admission control

In this paper we consider large deviations and admission control problems for a discrete-time Markovian polling system. The system consists of two-parallel queues and multiple heterogeneous servers. The arrival process of each queue is a superposition of mutually independent Markovian on/off processes, and the multiple servers serve independently the two queues according to the so called Bernoulli service schedule. Using the large deviations techniques, we derive upper and lower bounds of the overflow probabilities, and then we present an admission control criterion by which different Quality of Service (QoS) requirements for the two queues are guaranteed.     

Queues with service times and interarrival times depending linearly and randomly upon waiting times

We consider a modification of the standardG/G/1 queue with unlimited waiting space and the first-in first-out discipline in which the service times and interarrival times depend linearly and randomly on the waiting times. In this model the waiting times satisfy a modified version of the classical Lindley recursion. We determine when the waiting-time distributions converge to a proper limit and we develop approximations for this steady-state limit, primarily by applying previous results of Vervaat [21] and Brandt [4] for the unrestricted recursionY _n+1=C _n Y _n +X _n . Particularly appealing for applications is a normal approximation for the stationary waiting time distribution in the case when the queue only rarely becomes empty. We also consider the problem of scheduling successive interarrival times at arrival epochs, with the objective of achieving nearly maximal throughput with nearly bounded waiting times, while making the interarrival time sequence relatively smooth. We identify policies depending linearly and deterministically upon the work in the system which meet these objectives reasonably well; with these policies the waiting times are approximately contained in a specified interval a specified fraction of time.     

Polling systems with state-dependent setup times

We analyze a polling system with multiple stations (queues) attended by a cycling server, in which a setup occurs only when the queue that is polled by the server has one or more customers present. Although such systems are appropriate for modeling numerous manufacturing and telecommunication systems, their analysis is not well developed in the literature. We provide an exact analysis for the 2 station model and present two approximation schemes to determine the mean station waiting times for models with 3 or more stations. We show that some approximate models which have been proposed in the literature for providing upper bounds on the mean station waiting times do not always yield upper bounds. Extensive numerical tests indicate that a simple average of the two approximation schemes yields a close estimate of the true mean station waiting time. This average-of-approximations procedure appears to be robust for a large range of parameter values.Research supported in part by the Natural Sciences and Engineering Research Council of Canada under grant OGP0045904.Research supported in part by the National Science Foundation under grant DMI-9500471.     

Expected waiting time in symmetric polling systems with correlated walking times

Polling systems have been extensively studied, and have found many applications. They have often been used for studying wired local area networks such as token passing rings and wireless local area networks such as bluetooth. In this contribution we relax one of the main restrictions on the statistical assumptions under which polling systems have been analyzed. Namely, we allow correlation between walking times. We consider (i) the gated regime where a gate closes whenever the server arrives at a queue. It then serves at that queue all customers who were present when the gate closes. (ii) The exhaustive regime in which the server remains at a queue till it empties. Our analysis is based on stochastic recursive equations related to branching processes with migration with a random environment. In addition to our derivation of expected waiting times for polling systems with correlated walking times, we set the foundations for computing second order statistics of the general multi-dimensional stochastic recursions.      

Calculation of delay characteristics for multiserver queues with constant service times

We consider a discrete-time infinite-capacity queueing system with a general uncorrelated arrival process, constant-length service times of multiple slots, multiple servers and a first-come-first-served queueing discipline. Under the assumption that the queueing system can reach a steady state, we first establish a relationship between the steady-state probability distributions of the system content and the customer delay. Next, by means of this relationship, an explicit expression for the probability generating function of the customer delay is obtained from the known generating function of the system content, derived in previous work. In addition, several characteristics of the customer delay, namely the mean value, the variance and the tail distribution of the delay, are derived through some mathematical manipulations. The analysis is illustrated by means of some numerical examples.