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.     

Departure Processes of BMAP/G/1 Queues

A unified approach is applied to analyze the departure processes of finite/infinite BMAP/G/1 queueing systems for both vacationless and vacation arrangements via characterizing the moments, the z-transform of the scaled autocovariance function of interdeparture times C _P (z), and lag n (n1) covariance of interdeparture times. From a structural point of view, knowing departure process helps one to understand the impact of service mechanisms on arrivals. Through numerical experiments, we investigate and discuss how the departure statistics are affected by service and vacation distributions as well as the system capacity. From a practical perspective, output process analysis serves to bridge the nodal performance and connectionwise performance. Our results can be then used to facilitate connection- or networkwise performance analysis in the current high-speed networks.     

Analyzing the finite buffer batch arrival queue under Markovian service process: GIX/MSP/1/N

We consider a batch arrival finite buffer single server queue with inter-batch arrival times are generally distributed and arrivals occur in batches of random size. The service process is correlated and its structure is presented through Markovian service process (MSP). The model is analyzed for two possible customer rejection strategies: partial batch rejection and total batch rejection policy. We obtain steady-state distribution at pre-arrival and arbitrary epochs along with some important performance measures, like probabilities of blocking the first, an arbitrary, and the last customer of a batch, average number of customers in the system, and the mean waiting times in the system. Some numerical results have been presented graphically to show the effect of model parameters on the performance measures. The model has potential application in the area of computer networks, telecommunication systems, manufacturing system design, etc.      

TheM/G/1 queue with processor sharing and its relation to a feedback queue

The central model of this paper is anM/M/1 queue with a general probabilistic feedback mechanism. When a customer completes his ith service, he departs from the system with probability 1–p(i) and he cycles back with probabilityp(i). The mean service time of each customer is the same for each cycle. We determine the joint distribution of the successive sojourn times of a tagged customer at his loops through the system. Subsequently we let the mean service time at each loop shrink to zero and the feedback probabilities approach one in such a way that the mean total required service time remains constant. The behaviour of the feedback queue then approaches that of anM/G/1 processor sharing queue, different choices of the feedback probabilities leading to different service time distributions in the processor sharing model. This is exploited to analyse the sojourn time distribution in theM/G/1 queue with processor sharing.Some variants are also considered, viz., anM/M/1 feedback queue with additional customers who are always present, and anM/G/1 processor sharing queue with feedback.     

A BMAP/SM/1 queue with service times depending on the arrival process

We study a BMAP/>SM/1 queue with batch Markov arrival process input and semi‐Markov service. Service times may depend on arrival phase states, that is, there are many types of arrivals which have different service time distributions. The service process is a heterogeneous Markov renewal process, and so our model necessarily includes known models. At first, we consider the first passage time from level {κ+1} (the set of the states that the number of customers in the system is κ+1) to level {κ} when a batch arrival occurs at time 0 and then a customer service included in that batch simultaneously starts. The service descipline is considered as a LIFO (Last‐In First‐Out) with preemption. This discipline has the fundamental role for the analysis of the first passage time. Using this first passage time distribution, the busy period length distribution can be obtained. The busy period remains unaltered in any service disciplines if they are work‐conserving. Next, we analyze the stationary workload distribution (the stationary virtual waiting time distribution). The workload as well as the busy period remain unaltered in any service disciplines if they are work‐conserving. Based on this fact, we derive the Laplace–Stieltjes transform for the stationary distribution of the actual waiting time under a FIFO discipline. In addition, we refer to the Laplace–Stieltjes transforms for the distributions of the actual waiting times of the individual types of customers. Using the relationship between the stationary waiting time distribution and the stationary distribution of the number of customers in the system at departure epochs, we derive the generating function for the stationary joint distribution of the numbers of different types of customers at departures. This revised version was published online in June 2006 with corrections to the Cover Date.     

An M/G/1-type queuing model with service times depending on queue length

A study is made of an M/G/1-type queuing model in which customers receive one type of service until such time as, at the end of a service, the queue size is found to exceed a given value N, N ≥ 1. Then a second type of service is put into effect and remains in use until the queue size is reduced to a fixed value K, 0 ≤ K ≤ N. Equations are derived for the stationary probabilities both at departure times and at general times. An algorithm is developed that allows the rapid computation of the mean queue length and some important probabilities.     

Markov-modulatedPH/G/1 queueing systems

We study a PH/G/1 queue in which the arrival process and the service times depend on the state of an underlying Markov chain J(t) on a countable state spaceE. We derive the busy period process, waiting time and idle time of this queueing system. We also study the Markov modulated E_K/G/1 queueing system as a special case.     

M/G/1/N vacation model with varying E-limited service discipline

We define and analyze anM/G/1/N vacation model that uses a service discipline that we call theE-limited with limit variation discipline. According to this discipline, the server provides service until either the system is emptied (i.e. exhausted) or a randomly chosen limit ofl customers has been served. The server then goes on a vacation before returning to service the queue again. The queue length distribution and the Laplace-Stieltjes transforms of the waiting time, busy period and cycle time distributions are found. Further, an expression for the mean waiting time is developed. Several previously analyzed service disciplines, including Bernoulli scheduling, nonexhaustive service and limited service, are special cases of the general varying limit discipline that is analyzed in this paper.     

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.     

Effects of service disciplines inG/GI/s queueing systems

Transient extremal properties of some service disciplines are established in theG/GI/s queueing system for the minimization and maximization of the expectations of the Schur convex functions, convex symmetric functions and the sums of convex functions of the waiting times, response times, lag times and latenesses. When resequencing is required in the system, the FCFS and LCFS disciplines are shown to minimize and maximize, respectively, the expectations of any increasing functions of the end-to-end delays. All of these results are presented in terms of stochastic orderings. The paper concludes with extensions of the results to the stationary regime and to tandem as well as general queueing networks.This work was supported in part by the National Science Foundation under grant ASC 88-8802764.The work of this author was also partially supported by CEC DG-XIII under the ESPRIT-BRA grant QMIPS.     

Symmetric queues served in cyclic order

Consider a symmetrical system of n queues served in cyclic order by a single server. It is shown that the stationary number of customers in the system is distributed as the sum of three independent random variables, one being the stationary number of customers in a standard M/G/1 queue. This fact is used to establish an upper bound for the mean waiting time for the case where at most k customers are served at each queue per visit by the server. This approach is also used to rederive the mean waiting times for the cases of exhaustive service, gated service, and serve at most one customer at each queue per visit by the server.     

Discrete-time analysis of the GI/G/1 system with Bernoulli retrials: An algorithmic approach

In this paper, we show that the discrete GI/G/1 system with Bernoulli retrials can be analyzed as a level-dependent QBD process with infinite blocks; these blocks are finite when both the inter-arrival and service times have finite supports. The resulting QBD has a special structure which makes it convenient to analyze by the Matrix-analytic method (MAM). By representing both the inter-arrival and service times using a Markov chain based approach we are able to use the tools for phase type distributions in our model. Secondly, the resulting phase type distributions have additional structures which we exploit in the development of the algorithmic approach. The final working model approximates the level-dependent Markov chain with a level independent Markov chain that has a large set of boundaries. This allows us to use the modified matrix-geometric method to analyze the problem. A key task is selecting the level at which this level independence should begin. A procedure for this selection process is presented and then the distribution of the number of jobs in the orbit is obtained. Numerical examples are presented to demonstrate how this method works.     

Stationary distribution of queue length in G / M / 1 queue with two-stage service policy

We consider a G / M / 1 queue with two-stage service policy. The server starts to serve with rate of μ₁ customers per unit time until the number of customers in the system reaches λ. At this moment, the service rate is changed to that of μ₂ customers per unit time and this rate continues until the system is empty. We obtain the stationary distribution of the number of customers in the system.     

The M/G/1 Queue with Finite Workload Capacity

We consider the M/G/1 queueing system in which customers whose admission to the system would increase the workload beyond a prespecified finite capacity limit are not accepted. Various results on the distribution of the workload are derived; in particular, we give explicit formulas for its stationary distribution for M/M/1 and in the general case, under the preemptive LIFO discipline, for the joint stationary distribution of the number of customers in the system and their residual service times. Furthermore, the Laplace transform of the length of a busy period is determined. Finally, for M/D/1 the busy period distribution is derived in closed form.     

MAP/(PH/PH)/c Queue with Self-Generation of Priorities and Non-Preemptive Service

Abstract

Customers arriving according to a Markovian arrival process are served at a c server facility. Waiting customers generate into priority while waiting in the system (self-generation of priorities), at a constant rate γ; such a customer is immediately taken for service, if at least one of the servers is free. Else it waits at a waiting space of capacity c exclusively for priority generated customers, provided there is vacancy. A customer in service is not preempted to accommodate a priority generated customer. The service times of ordinary and priority generated customers follow distinct PH-distributions. It is proved that the system is always stable. We provide a numerical procedure to compute the optimal number of servers to be employed to minimize the loss to the system. Several performance measures are evaluated.     

Index Heuristics for Multiclass M/G/1 Systems with Nonpreemptive Service and Convex Holding Costs

We consider the optimal service control of a multiclass M/G/1 queueing system in which customers are served nonpreemptively and the system cost rate is additive across classes and increasing convex in the numbers present in each class. Following Whittle's approach to a class of restless bandit problems, we develop a Langrangian relaxation of the service control problem which serves to motivate the development of a class of index heuristics. The index for a particular customer class is characterised as a fair charge for service of that class. The paper develops these indices and reports an extensive numerical investigation which exhibits strong performance of the index heuristics for both discounted and average costs.     

Sojourn time asymptotics in the M/G/1 processor sharing queue

We show for the M/G/1 processor sharing queue that the service time distribution is regularly varying of index -ν, ν non-integer, iff the sojourn time distribution is regularly varying of index -ν. This result is derived from a new expression for the Laplace–Stieltjes transform of the sojourn time distribution. That expression also leads to other new properties for the sojourn time distribution. We show how the moments of the sojourn time can be calculated recursively and prove that the kth moment of the sojourn time is finite iff the kth moment of the service time is finite. In addition, we give a short proof of a heavy traffic theorem for the sojourn time distribution, prove a heavy traffic theorem for the moments of the sojourn time, and study the properties of the heavy traffic limiting sojourn time distribution when the service time distribution is regularly varying. Explicit formulas and multiterm expansions are provided for the case that the service time has a Pareto distribution. This revised version was published online in June 2006 with corrections to the Cover Date.     

A reader-writer queue with reader preference

This paper considers a reader-writer queue with reader preference. The system can process an unlimited number of readers simultaneously. However, writers have to be processed one at a time. Readers are given non-preemptive priority over writers. Both readers and writers arrive according to Poisson processes (PP) and have general independent service times. There is infinite waiting room for both. This system is analyzed to produce stability conditions. The analysis uses anM/G/ queue busy period to model readers, followed by a modifiedM/G/1 queue to model the entire system. Finally, results are presented for the expected wait-in-queue times for the readers and writers. The paper ends with an example.This work was done while the author was visiting the IBM Corporation, Networking Systems, RTP, NC 27709, USA.     

Priority queues with semi-exhaustive service

This paper studies a new type of multi-class priority queues with semi-exhaustive service and server vacations, which operates as follows: A single server continues serving messages in queuen until the number of messages decreases toone less than that found upon the server's last arrival at queuen, where 1nN. In succession, messages of the highest class present in the system, if any, will be served according to this semi-exhaustive service. Applying the delay cycle analysis and introducing a super-message composed of messages served in a busy period, we derive explicitly the Laplace-Stieltjes transforms (LSTs) and the first two moments of the message waiting time distributions for each class in the M/G/1-type priority queues with multiple and single vacations. We also derive a conversion relationship between the LSTs for waiting times in the multiple and single vacation models.