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 single server queue in a hard-real-time environment

We consider a single server first in first out queue in which each arriving task has to be completed within a certain period of time (its deadline). More precisely, each arriving task has its own deadline - a non-negative real number - and as soon as the response time of one task exceeds its deadline, the whole system in considered to have failed. (In that sense the deadline is hard.) The main practical motivation for analyzing such queues comes from the need to evaluate mathematically the reliability of computer systems working with real time constraints (space or aircraft systems for instance). We shall therefore be mainly concerned with the analytical characterization of the transient behavior of such a queue in order to determine the probability of meeting all hard deadlines during a finite period of time (the ‘mission time’). The probabilistic methods for analyzing such systems are suggested by earlier work on impatience in telecommunication systems [1,2].     

A Markovian single server with upstream job and downstream demand arrival stream

In this paper we consider a Markovian single server system which processes items arriving from an upstream region (as usual in queueing systems) and is controlled by a demand arrival stream for finished items from a downstream area. A finite storage is available at the server to store finished items not immediately needed in the downstream area. The system considered corresponds to an assembly-like queue with two input streams. The system is stable in a strict sense only if all queues are finite, i.e., both random processes are synchronized via blocking. This notion leads to a complementary system with a very similar state space which is a pair of Markovian single servers with synchronous arrivals. In the mathematical analysis the main focus is on the state probabilities and expectation of minimum and maximum of the two input queues. This revised version was published online in June 2006 with corrections to the Cover Date.     

Discrete NT-policy single server queue with Markovian arrival process and phase type service

We consider a discrete time single server queueing system in which arrivals are governed by the Markovian arrival process. During a service period, all customers are served exhaustively. The server goes on vacation as soon as he/she completes service and the system is empty. Termination of the vacation period is controlled by two threshold parameters N and T, i.e. the server terminates his/her vacation as soon as the number waiting reaches N or the waiting time of the leading customer reaches T units. The steady state probability vector is shown to be of matrix-geometric type. The average queue length and the probability that the server is on vacation (or idle) are obtained. We also derive the steady state distribution of the waiting time at arrivals and show that the vacation period distribution is of phase type.     

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.     

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.     

Peak congestion in multi-server service systems with slowly varying arrival rates

In this paper we consider the M _t queueing model with infinitely many servers and a nonhomogeneous Poisson arrival process. Our goal is to obtain useful insights and formulas for nonstationary finite-server systems that commonly arise in practice. Here we are primarily concerned with the peak congestion. For the infinite-server model, we focus on the maximum value of the mean number of busy servers and the time lag between when this maximum occurs and the time that the maximum arrival rate occurs. We describe the asymptotic behavior of these quantities as the arrival changes more slowly, obtaining refinements of previous simple approximations. In addition to providing improved approximations, these refinements indicate when the simple approximations should perform well. We obtain an approximate time-dependent distribution for the number of customers in service in associated finite-server models by using the modified-offered-load (MOL) approximation, which is the finite-server steady-state distribution with the infinite-server mean serving as the offered load. We compare the value and lag in peak congestion predicted by the MOL approximation with exact values for M _t/M/s delay models with sinusoidal arrival-rate functions obtained by numerically solving the Chapman–Kolmogorov forward equations. The MOL approximation is remarkably accurate when the delay probability is suitably small. To treat systems with slowly varying arrival rates, we suggest focusing on the form of the arrival-rate function near its peak, in particular, on its second and third derivatives at the peak. We suggest estimating these derivatives from data by fitting a quadratic or cubic polynomial in a suitable interval about the peak. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

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.     

A queueing network with a single cyclically roving server

A queueingnetwork that is served by asingle server in a cyclic order is analyzed in this paper. Customers arrive at the queues from outside the network according to independent Poisson processes. Upon completion of his service, a customer mayleave the network, berouted to another queue in the network orrejoin the same queue for another portion of service. The single server moves through the different queues of the network in a cyclic manner. Whenever the server arrives at a queue (polls the queue), he serves the waiting customers in that queue according to some service discipline. Both the gated and the exhaustive disciplines are considered. When moving from one queue to the next queue, the server incurs a switch-over period. This queueing network model has many applications in communication, computer, robotics and manufacturing systems. Examples include token rings, single-processor multi-task systems and others. For this model, we derive the generating function and the expected number of customers present in the network queues at arbitrary epochs, and compute the expected values of the delays observed by the customers. In addition, we derive the expected delay of customers that follow a specific route in the network, and we introduce pseudo-conservation laws for this network of queues.Summary of notation B_i, B _i ^* (s) service time of a customer at queue i and its LST - b_i, b_i ⁽²⁾ mean and second moment of B_i - R_i, R _i ^* (s) duration of switch-over period from queue i and its LST - r_i, r_i mean and second moment of R_i - r, r⁽²⁾ mean and second moment of _i ^N =₁R_i - _i external arrival rate of type-i customers - _i total arrival rate into queue i - _i utilization of queue i; _i=_i - system utilization _i ^N =_1i - c=E[C] the expected cycle length - X _i ^j number of customers in queue j when queue i is polled - X_i=X _i ⁱ number of customers residing in queue i when it is polled - f_i(j) - X _i ^* number of customers residing in queue i at an arbitrary moment - Y_i the duration of a service period of queue i - W_i,T_i the waiting time and sojourn time of an arbitary customer at queue i - F^*(z₁, z₂,..., z_N) GF of number of customers present at the queues at arbitrary moments - F_i(z₁, z₂,..., z_N) GF of number of customers present at the queues at polling instants of queue i - ¯F_i(z₁, z₂,...,z_N) GF of number of customers present at the queues at switching instants of queue i - V_i(z₁, z₂,..., z_N) GF of number of customers present at the queues at service initiation instants at queue i - ¯V_i(z₁,z₂,...,z_N) GF of number of customers present at the queues at service completion instants at queue i The work of this author was supported by the Bernstein Fund for the Promotion of Research and by the Fund for the Promotion of Research at the Technion.Part of this work was done while H. Levy was with AT&T Bell Laboratories.     

An approximate analysis of a cyclic server queue with limited service and reservations

In this paper, we examine a queueing problem motivated by the pipeline polling protocol in satellite communications. The model is an extension of the cyclic queueing system withM-limited service. In this service mechanism, each queue, after receiving service on cyclej, makes a reservation for its service requirement in cyclej + 1. The main contribution to queueing theory is that we propose an approximation for the queue length and sojourn-time distributions for this discipline. Most approximate studies on cyclic queues, which have been considered before, examine the means only. Our method is an iterative one, which we prove to be convergent by using stochastic dominance arguments. We examine the performance of our algorithm by comparing it to simulations and show that the results are very good.     

A single server queue with gated processor-sharing discipline

In this paper we consider a single server queue in which arrivals occur according to a Poisson process and each customer's service time is exponentially distributed. The server works according to the gated process-sharing discipline. In this discipline, the server provides service to a batch of at mostm customers at a time. Once a batch of customers begins service, no other waiting customer can receive service until all members of the batch have completed their service. For this queue, we derive performance characteristics, such as waiting time distribution, queue length distribution etc. For this queue, it is possible to obtain the mean conditional response time for a customer whose service time is known. This conditional response time is a nonlinear function (as opposed to the linear case for the ordinary processor-sharing queue). A special case of the queue (wherem=) has an interesting and unusual solution. For this special case, the size of the batch for service is a Markov chain whose steady state distribution can be explicitly written down. Apart from the contribution to the theory of Markov chains and queues, the model may be applicable to scheduling of computer and communication systems.     

AN M/G/1 RETRIAL QUEUE WITH SECOND MULTI-OPTIONAL SERVICE, FEEDBACK AND UNRELIABLE SERVER

An M/G/1 retrial queue with two-phase service and feedback is studied in this paper, where the server is subject to starting failures and breakdowns during service. Primary customers get in the system according to a Poisson process, and they will receive service immediately if the server is available upon arrival. Otherwise, they will enter a retrial orbit and are queued in the orbit in accordance with a first-come-first-served （FCFS） discipline. Customers are allowed to balk and renege at particular times. All customers demand the first “essential” service, whereas only some of them demand the second “multi-optional” service. It is assumed that the retrial time, service time and repair time of the server are all arbitrarily distributed. The necessary and sufficient condition for the system stability is derived. Using a supplementary variable method, the steady-state solutions for some queueing and reliability measures of the system are obtained.     

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 infinite-buffer single server queue with a variant of multiple vacation policy and batch Markovian arrival process

We consider an infinite-buffer single server queue where arrivals occur according to a batch Markovian arrival process (BMAP). The server serves until system emptied and after that server takes a vacation. The server will take a maximum number H of vacations until either he finds at least one customer in the queue or the server has exhaustively taken all the vacations. We obtain queue length distributions at various epochs such as, service completion/vacation termination, pre-arrival, arbitrary, departure, etc. Some important performance measures, like mean queue lengths and mean waiting times, etc. have been obtained. Several other vacation queueing models like, single and multiple vacation model, queues with exceptional first vacation time, etc. can be considered as special cases of our model.     

Two queues with alternating service and server breakdown

We consider a queueing system with two stations served by a single server in a cyclic manner. We assume that at most one customer can be served at a station when the server arrives at the station. The system is subject to service interuption that arises from server breakdown. When a server breakdown occurs, the server must be repaired before service can resume. We obtain the approximate mean delay of customers in the system.     

A single server queue with platooned arrivals and phase type services

A semi-Markovian point process which qualitatively models platooned arrivals is introduced. This process is used as the input to a single server queue in which the service times are independent and have a common distribution of phase type.It is shown that this queue has an embedded Markov chain of a particular block-partitioned type, whose invariant probability vector in the stable case is of matrix-geometric form. Detailed algorithms for the computation of the steady-state features of the queue are obtained and a representative numerical example is discussed.     

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.     

Optimal strategy policy in batch arrival queue with server breakdowns and multiple vacations

This paper considers a like-queue production system in which server vacations and breakdowns are possible. The decision-maker can turn a single server on at any arrival epoch or off at any service completion. We model the system by an M^[x]/M/1 queueing system with N policy. The server can be turned off and takes a vacation with exponential random length whenever the system is empty. If the number of units waiting in the system at any vacation completion is less than N, the server will take another vacation. If the server returns from a vacation and finds at least N units in the system, he immediately starts to serve the waiting units. It is assumed that the server breaks down according to a Poisson process and the repair time has an exponential distribution. We derive the distribution of the system size through the probability generating function. We further study the steady-state behavior of the system size distribution at random (stationary) point of time as well as the queue size distribution at departure point of time. Other system characteristics are obtained by means of the grand process and the renewal process. Finally, the expected cost per unit time is considered to determine the optimal operating policy at a minimum cost. The sensitivity analysis is also presented through numerical experiments.     

A single server queue with random arrivals and balking: Confidence interval estimation

This paper investigates a queueing system, which consists of Poisson input of customers, some of whom are lost to balking, and a single server working a shift of lengthL and providing a service whose duration can vary from customer to customer. If a service is in progress at the end of a shift, the server works overtime to complete the service. This process was motivated by the behavior of fishermen interviewed in the NY Great Lakes Creel Survey.We derive the distributions of the number of services (X), overtime and total server idle time (T), both unconditionally (for Poisson arrivals) and conditionally on the number (n) of arrivals per shift, assuming that the arrival times are not recorded in the data. These distributions provide the basis for estimation of the parameters from asingle realization of the queueing process during [0,L]. The conditional distributions also can be used to estimate common service time,w, when (n, X) or (n, T) are observed. Confidence intervals based onT are of shorter length, for all confidence coefficients, than the corresponding intervals based onX.This paper is Technical Report #BU-1019-M in the Biometrics Unit Series. The authors are grateful to N.U. Prabhu for suggestions on streamlining the distributional derivations and to D.R. Cox and C.E. McCulloch for helpful comments.