Comparative analysis for the N policy M/G/1 queueing system with a removable and unreliable server

In this paper we analyze a single removable and unreliable server in the N policy M/G/1 queueing system in which the server breaks down according to a Poisson process and the repair time obeys an arbitrary distribution. The method of maximum entropy is used to develop the approximate steady-state probability distributions of the queue length in the M/G(G)/1 queueing system, where the second and the third symbols denote service time and repair time distributions, respectively. A study of the derived approximate results, compared to the exact results for the M/M(M)/1, M/E₂(E₃)/1, M/H₂(H₃)/1 and M/D(D)/1 queueing systems, suggest that the maximum entropy principle provides a useful method for solving complex queueing systems. Based on the simulation results, we demonstrate that the N policy M/G(G)/1 queueing model is sufficiently robust to the variations of service time and repair time distributions.     

Operating characteristics of MX/G/1 queue with N-policy

We consider aM ^X/G/1 queueing system withN-policy. The server is turned off as soon as the system empties. When the queue length reaches or exceeds a predetermined valueN (threshold), the server is turned on and begins to serve the customers. We place our emphasis on understanding the operational characteristics of the queueing system. One of our findings is that the system size is the sum of two independent random variables: one has thePGF of the stationary system size of theM ^X/G/1 queueing system withoutN-policy and the other one has the probability generating function _j=0 ^N=1 _j z ^j/ _j=0 ^N=1 _j , in which _j is the probability that the system state stays atj before reaching or exceedingN during an idle period. Using this interpretation of the system size distribution, we determine the optimal thresholdN under a linear cost structure.     

Optimal Control of an M/G/1/K Queueing System with Combined <Emphasis Type="Italic">F</Emphasis> Policy and Startup Time

We investigate the optimal management problem of an M/G/1/K queueing system with combined F policy and an exponential startup time. The F policy queueing problem investigates the most common issue of controlling the arrival to a queueing system. We present a recursive method, using the supplementary variable technique and treating the supplementary variable as the remaining service time, to obtain the steady state probability distribution of the number of customers in the system. The method is illustrated analytically for exponential service time distribution. A cost model is established to determine the optimal management F policy at minimum cost. We use an efficient Maple computer program to calculate the optimal value of F and some system performance measures. Sensitivity analysis is also investigated.     

Combined Elapsed Time and Matrix-Analytic Method for the Discrete Time GI/G/1 and GI X /G/1 Systems

In this paper, we show that the discrete GI/G/1 system can be easily analysed as a QBD process with infinite blocks by using the elapsed time approach in conjunction with the Matrix-geometric approach. The positive recurrence of the resulting Markov chain is more easily established when compared with the remaining time approach. The G-measure associated with this Markov chain has a special structure which is usefully exploited. Most importantly, we show that this approach can be extended to the analysis of the GI ^X /G/1 system. We also obtain the distributions of the queue length, busy period and waiting times under the FIFO rule. Exact results, based on computational approach, are obtained for the cases of input parameters with finite support – these situations are more commonly encountered in practical problems.     

A BMAP/G/1 Retrial Queue with a Server Subject to Breakdowns and Repairs

In this paper, we consider a BMAP/G/1 retrial queue with a server subject to breakdowns and repairs, where the life time of the server is exponential and the repair time is general. We use the supplementary variable method, which combines with the matrix-analytic method and the censoring technique, to study the system. We apply the RG-factorization of a level-dependent continuous-time Markov chain of M/G/1 type to provide the stationary performance measures of the system, for example, the stationary availability, failure frequency and queue length. Furthermore, we use the RG-factorization of a level-dependent Markov renewal process of M/G/1 type to express the Laplace transform of the distribution of a first passage time such as the reliability function and the busy period.     

An MX/G/1 queueing system with a setup period and a vacation period

This paper deals with an M^X/G/1 queueing system with a vacation period which comprises an idle period and a random setup period. The server is turned off each time when the system becomes empty. At this point of time the idle period starts. As soon as a customer or a batch of customers arrive, the setup of the service facility begins which is needed before starting each busy period. In this paper we study the steady state behaviour of the queue size distributions at stationary (random) point of time and at departure point of time. One of our findings is that the departure point queue size distribution is the convolution of the distributions of three independent random variables. Also, we drive analytically explicit expressions for the system state probabilities and some performance measures of this queueing system. Finally, we derive the probability generating function of the additional queue size distribution due to the vacation period as the limiting behaviour of the M^X/M/1 type queueing system. This revised version was published online in June 2006 with corrections to the Cover Date.     

Relaxation Time for the Discrete D/G/1 Queue

When queueing models are used for performance analysis of some stochastic system, it is usually assumed that the system is in steady-state. Whether or not this is a realistic assumption depends on the speed at which the system tends to its steady-state. A characterization of this speed is known in the queueing literature as relaxation time.The discrete D/G/1 queue has a wide range of applications. We derive relaxation time asymptotics for the discrete D/G/1 queue in a purely analytical way, mostly relying on the saddle point method. We present a simple and useful approximate upper bound which is sharp in case the load on the system is not very high. A sharpening of this upper bound, which involves the complementary error function, is then developed and this covers both the cases of low and high loads.For the discrete D/G/1 queue, the stationary waiting time distribution can be expressed in terms of infinite series that follow from Spitzer’s identity. These series involve convolutions of the probability distribution of a discrete random variable, which makes them suitable for computation. For practical purposes, though, the infinite series should be truncated. The relaxation time asymptotics can be applied to determine an appropriate truncation level based on a sharp estimate of the error caused by truncating.This revised version was published online in June 2005 with corrected coverdate     

On inference concerning time-dependent queue performance: The M/G/1 example

This paper proposes easily-computed approximations to the finite-time expected waiting time for anM/G/1 system starting from an empty state. Both unsaturated (ρ<1) and saturated (ρ>1) conditions are considered. Numerical evidence is presented to indicate that the quality of the approximations is usefully good, especially when ease of computation is an issue. Further, the methodology is adapted to assess expected waiting time when inference must be made from a random sample of service times, and the decision is made to do so nonparametrically, i.e., without fitting a specific function. The results appear reasonable and potentially useful, and are not burdensome to obtain. The methodology investigated can also be applied to the variety of queueing models that are close siblings ofM/G/1: priority and breakdowns and “vacations” being examples. Of course other approximating and inferential options remain to be investigated.     

Analysis of the M x /G/1 Queue with a Random Setup Time

Abstract

We consider an M ^x /G/1 queueing system with a random setup time, where the service of the first unit at the commencement of each busy period is preceded by a random setup time, on completion of which service starts. For this model, the queue size distributions at a random point of time as well as at a departure epoch and some important performance measures are known [see Choudhury, G. An M ^x /G/1 queueing system with setup period and a vacation period. Queueing Sys. 2000, 36, 23–38]. In this paper, we derive the busy period distribution and the distribution of unfinished work at a random point of time. Further, we obtain the queue size distribution at a departure epoch as a simple alternative approach to Choudhury4 Choudhury, G. 2000. An M^x/G/1 queueing system with setup period and a vacation period. Queueing Syst., 36: 23–38. [CROSSREF][Crossref], [Web of Science ®] , [Google Scholar]. Finally, we present a transform free method to obtain the mean waiting time of this model.     

Age Process, Workload Process, Sojourn Times, and Waiting Times in a Discrete Time SM[K]/PH[K]/1/FCFS Queue

In this paper, we study a discrete time queueing system with multiple types of customers and a first-come-first-served (FCFS) service discipline. Customers arrive according to a semi-Markov arrival process and the service times of individual customers have PH-distributions. A GI/M/1 type Markov chain for a generalized age process of batches of customers is introduced. The steady state distribution of the GI/M/1 type Markov chain is found explicitly and, consequently, the steady state distributions of the age of the batch in service, the total workload in the system, waiting times, and sojourn times of different batches and different types of customers are obtained. We show that the generalized age process and a generalized total workload process have the same steady state distribution. We prove that the waiting times and sojourn times have PH-distributions and find matrix representations of those PH-distributions. When the arrival process is a Markov arrival process with marked transitions, we construct a QBD process for the age process and the total workload process. The steady state distributions of the waiting times and the sojourn times, both at the batch level and the customer level, are obtained from the steady state distribution of the QBD process. A number of numerical examples are presented to gain insight into the waiting processes of different types of customers.AMS subject classification: 60K25, 60J10This revised version was published online in June 2005 with corrected coverdate     

The MacLaurin expansion for a G/G/1 queue with Markov-modulated arrivals and services

Consider a Markov-modulated G/G/1 queueing system in which the arrival and the service mechanisms are controlled by an underlying Markov chain. The classical approaches to the waiting time of this type of queueing system have severe computational difficulties. In this paper, we develop a numerical algorithm to calculate the moments of the waiting time based on Gong and Hu's idea. Our numerical results show that the algorithm is powerful. A matrix recursive equation for the moments of the waiting time is also given under certain conditions.     

Optimal control of the N policy M/G/1 queueing system with server breakdowns and general startup times

This paper deals with an N policy M/G/1 queueing system with a single removable and unreliable server whose arrivals form a Poisson process. Service times, repair times, and startup times are assumed to be generally distributed. When the queue length reaches N(N ? 1), the server is immediately turned on but is temporarily unavailable to serve the waiting customers. The server needs a startup time before providing service until there are no customers in the system. We analyze various system performance measures and investigate some designated known expected cost function per unit time to determine the optimal threshold N at a minimum cost. Sensitivity analysis is also studied.     

The Discrete-Time GI/Geo/1 Queue with Multiple Vacations

We study a discrete-time GI/Geo/1 queue with server vacations. In this queueing system, the server takes vacations when the system does not have any waiting customers at a service completion instant or a vacation completion instant. This type of discrete-time queueing model has potential applications in computer or telecommunication network systems. Using matrix-geometric method, we obtain the explicit expressions for the stationary distributions of queue length and waiting time and demonstrate the conditional stochastic decomposition property of the queue length and waiting time in this system.     

A NEW APPROACH FOR THE STUDY OF THE M X /G/1 QUEUE USING RENEWAL ARGUMENTS

The M ^X /G/1 queueing system as well as several of its variants have long ago been studied by considering the embedded discrete-time Markov chain at service completion epochs. Alternatively other approaches have been proposed such as the theory of regenerative processes, the supplementary variable method, properties of the busy period, etc. In this note we study the M ^X /G/1 queue via a simple new method that uses renewal arguments. This approach seems quite powerful and may become fruitful in the investigation of other queueing systems as well.     

Lattice path counting andM/M/c queueing systems

We apply the lattice path counting method to the analysis of the transientM/M/c queueing system. A closed-form solution is obtained for the probability of exactlyi arrivals andj departures within a time interval of lengtht in anM/M/c queueing system that is empty at the initial time. The derivation of the probability is based on the counting of paths from the origin to(i,j) on thexy-plane, that have exactly r_d x-steps whose depth from the liney=x isd (d=0,1,...,c–1). The closed-form solution has an expression useful for numerical calculation.     

A markov-modulated M/M/1 queue with group arrivals

We study anM/M/1 group arrival queue in which the arrival rate, service time distributions and the size of each group arrival depend on the state of an underlying finite-state Markov chain. Using Laplace transforms and matrix analysis, we derive the results for the queue length process, its limit distribution and the departure process. In some special cases, explicit results are obtained which are analogous to known classic results.     

A recursive method for the F-policy G/M/1/K queueing system with an exponential startup time

This paper deals with the optimal control of a finite capacity G/M/1 queueing system combined the F-policy and an exponential startup time before start allowing customers in the system. The F-policy queueing problem investigates the most common issue of controlling arrival to a queueing system. We provide a recursive method, using the supplementary variable technique and treating the supplementary variable as the remaining interarrival time, to develop the steady-state probability distribution of the number of customers in the system. We illustrate a recursive method by presenting three simple examples for exponential, 3-stage Erlang, and deterministic interarrival time distributions, respectively. A cost model is developed to determine the optimal management F-policy at minimum cost. We use an efficient Maple computer program to determine the optimal operating F-policy and some system performance measures. Sensitivity analysis is also studied.     

Wiener-Hopf analysis of an M/G/1 queue with negative customers and of a related class of random walks

Two variants of an M/G/1 queue with negative customers lead to the study of a random walkX _n+1=[X _n + _n ]⁺ where the integer-valued _n are not bounded from below or from above, and are distributed differently in the interior of the state-space and on the boundary. Their generating functions are assumed to be rational. We give a simple closed-form formula for , corresponding to a representation of the data which is suitable for the queueing model. Alternative representations and derivations are discussed. With this formula, we calculate the queue length generating function of an M/G/1 queue with negative customers, in which the negative customers can remove ordinary customers only at the end of a service. If the service is exponential, the arbitrarytime queue length distribution is a mixture of two geometrical distributions.Supported by the European grant BRA-QMIPS of CEC DG XIII.     

Optimal monotone hysteretic Markov policies in anM/M/1 queueing model with switching costs and finite time horizon

In anM/M/1 queueing model, a decision maker can choosem pairs of arrival- and service rates. He can change his action at any time epoch, a switch of action costs an amount depending on the size of the switch. Besides that there are continuously incurring costs. Over a finite time horizon, there exists an optimal monotone hysteretic Markov policy. This is shown essentially by the technique of time discretization.The work producing this article was done during a half year stay at the University of Leiden, The Netherlands, with Prof. Arie Hordijk. A technical report (a more detailled version of this article) was written there [6]. The opportunity for this stay was given by the University of Bonn, Germany, where the author, at that time, worked as scientific assistant of Prof. M. Schäl.