An improved truncation technique to analyze a Geo/PH/1 retrial queue with impatient customers

This paper considers a discrete-time retrial queue with impatient customers. We establish the global balance equations of the Markov chain describing the system evolution and prove that this queueing system is stable as long as the customers are strict impatient and the mean retrial time is finite. Direct truncation with matrix decomposition is used to approximate the steady-state distribution of the system state and hence derive a set of performance measures. The proposed matrix decomposition scheme is presented in a general form which is applicable to any finite Markov chain of the GI/M/1-type. It represents a generalization of the Gaver–Jacobs–Latouche's algorithm that deals with QBD process. Different sets of numerical results are presented to test the efficiency of this technique compared to the generalized truncation one. Moreover, an emphasis is put on the effect of impatience on the main performance measures.     

Analysis of discrete-time batch service renewal input queue with multiple working vacations

This paper investigates a discrete-time single server batch service queue with multiple working vacations wherein arrivals occur according to a discrete-time renewal process. The server works with a different service rate rather than completely stopping during the vacation period. The service is performed in batches and the server takes a vacation when the system does not have any waiting customers at a service completion epoch or a vacation completion epoch. We present a recursive method, using the supplementary variable technique to obtain the steady-state queue-length distributions at pre-arrival, arbitrary and outside observer’s observation epochs. The displacement operator method is used to solve simultaneous non-homogeneous difference equations. Some performance measures and waiting-time distribution in the system have also been discussed. Finally, numerical results showing the effect of model parameters on key performance measures are presented.     

Steady state analysis of the GI/M/1/N queue with a variant of multiple working vacations

This paper studies the GI/M/1/N queue with a variant of multiple working vacations, where the server leaves for a working vacation as soon as the system becomes empty. The server takes at most H consecutive working vacations if the system remains empty after the end of a working vacation. Employing the supplementary variable and embedded Markov chain methods, we obtain the queue length distribution at different time epochs. Based on the various system length distribution, the probability of blocking, mean waiting times and mean system lengths have been derived. Finally, numerical results are discussed.     

An MX/G/1 queue with randomized working vacations and at most J vacations

This paper treats a bulk arrival queue with randomized working vacation policy. Whenever the system becomes empty, the server takes a vacation. During the vacation period, customers are to be served at a lower rate. Once the vacation ends, the server will return to the normal working state and begin to serve the customers in the system if any. Otherwise, the server either remains idle with probability p or leaves for another vacation with probability 1?p. This pattern continues until the number of vacations taken reaches J. If the system is empty at the end of the Jth vacation, the server will wait idly for a new arrival. By using supplementary variable technique, we derive the system size distribution at arbitrary epoch, at departure epoch and at busy period initial epoch, as well as some important system characteristics. Numerical examples are provided to illustrate the influence of system parameters on several performance measures.     

An M/G/1 retrial G-queue with non-exhaustive random vacations and an unreliable server

This paper deals with an M/G/1 retrial queue with negative customers and non-exhaustive random vacations subject to the server breakdowns and repairs. Arrivals of both positive customers and negative customers are two independent Poisson processes. A breakdown at the busy server is represented by the arrival of a negative customer which causes the customer being in service to be lost. The server takes a vacation of random length after an exponential time when the server is up. We develop a new method to discuss the stable condition by finding absorb distribution and using the stable condition of a classical M/G/1 queue. By applying the supplementary variable method, we obtain the steady-state solutions for both queueing measures and reliability quantities. Moreover, we investigate the stochastic decomposition law. We also analyse the busy period of the system. Some special cases of interest are discussed and some known results have been derived. Finally, an application to cellular mobile networks is provided and the effects of various parameters on the system performance are analysed numerically.     

Markovian queue optimisation analysis with an unreliable server subject to working breakdowns and impatient customers

This study investigates an infinite capacity Markovian queue with a single unreliable service station, in which the customers may balk (do not enter) and renege (leave the queue after entering). The unreliable service station can be working breakdowns even if no customers are in the system. The matrix-analytic method is used to compute the steady-state probabilities for the number of customers, rate matrix and stability condition in the system. The single-objective model for cost and bi-objective model for cost and expected waiting time are derived in the system to fit in with practical applications. The particle swarm optimisation algorithm is implemented to find the optimal combinations of parameters in the pursuit of minimum cost. Two different approaches are used to identify the Pareto optimal set and compared: the epsilon-constraint method and non-dominate sorting genetic algorithm. Compared results allow using the traditional optimisation approach epsilon-constraint method, which is computationally faster and permits a direct sensitivity analysis of the solution under constraint or parameter perturbation. The Pareto front and non-dominated solutions set are obtained and illustrated. The decision makers can use these to improve their decision-making quality.     

Stationary distributions and optimal control of queues with batch Markovian arrival process under multiple adaptive vacations

We consider an infinite-buffer single server queue with batch Markovian arrival process (BMAP) and exhaustive service discipline under multiple adaptive vacation policy. That is, the server serves until system emptied and after that server takes a random maximum number H different vacations until either he finds at least one customer in queue or the server have exhaustively taken all the vacations. The maximum number H of vacations taken by the server is a discrete random variable. We obtain queue-length distributions at various epochs such as, service completion/vacation termination, pre-arrival, arbitrary, post-departure and pre-service. The proposed analysis is based on the use of matrix-analytic procedure to obtain queue-length distribution at a post-departure epoch. Later we use supplementary variable method and simple algebraic manipulations to obtain the queue-length distribution at other epochs using queue-length distribution at post-departure epoch. Some important performance measures, like mean queue lengths and mean waiting times have been obtained. Several other vacation queueing models can be obtained as a special case of our model, e.g., single-, multiple-vacation model and queues with exceptional first vacation time. Finally, the total expected cost function per unit time is considered to determine a locally optimal multiple adaptive vacation policy at a minimum cost.     

Analysis of the discrete-time Geo/G/1 working vacation queue and its application to network scheduling

In this paper we present an exact steady-state analysis of a discrete-time Geo/G/1 queueing system with working vacations, where the server can keep on working, but at a slower speed during the vacation period. The transition probability matrix describing this queuing model can be seen as an M/G/1-type matrix form. This allows us to derive the probability generating function (PGF) of the stationary queue length at the departure epochs by the M/G/1-type matrix analytic approach. To understand the stationary queue length better, by applying the stochastic decomposition theory of the standard M/G/1 queue with general vacations, another equivalent expression for the PGF is derived. We also show the different cases of the customer waiting to obtain the PGF of the waiting time, and the normal busy period and busy cycle analysis is provided. Finally, we discuss various performance measures and numerical results, and an application to network scheduling in the wavelength division-multiplexed (WDM) system illustrates the benefit of this model in real problems.     

The GI/M/1 queue and the GI/Geo/1 queue both with single working vacation

We first consider the continuous-time GI/M/1 queue with single working vacation (SWV). During the SWV, the server works at a different rate rather than completely stopping working. We derive the steady-state distributions for the number of customers in the system both at arrival and arbitrary epochs, and for the FIFO sojourn time for an arbitrary customer. We then consider the discrete-time GI/Geo/1/SWV queue by contrasting it with the GI/M/1/SWV queue.     

The analysis of the M/M/1 queue with two vacation policies (M/M/1/SWV+MV)

We consider an M/M/1 queue with two vacation policies which comprise single working vacation and multiple vacations, denoted by M/M/1/SMV+MV. Using two methods (called R-matrix method and G-matrix method), we obtain the stationary distribution of queue length (including the customer being in service) and make further analysis on the stationary numbers of customers in the working vacation and vacation period, respectively. The stochastic decomposition results of stationary queue length and the sojourn time of a customer are also derived. Meanwhile, we show that a simple and direct method of decomposition developed in Liu et al. [Stochastic decompositions in the M/M/1 queue with working vacations, Oper. Res. Lett. 35 (2007), pp. 595–600] is also applicable to our model. Furthermore, busy period is analysed by the limiting theorem of alternative renewal process. Finally, some boundary properties and numerical analysis on performance measures are presented.     

Note on the article: Maximum entropy analysis of the M/M/1 queueing system with multiple vacations and server breakdowns

Wang et al. [Wang, K. H., Chan, M. C., & Ke, J. C. (2007). Maximum entropy analysis of the M^[x]/M/1 queueing system with multiple vacations and server breakdowns. Computers & Industrial Engineering, 52, 192–202] elaborate on an interesting approach to estimate the equilibrium distribution for the number of customers in the M^[x]/M/1 queueing model with multiple vacations and server breakdowns. Their approach consists of maximizing an entropy function subject to constraints, where the constraints are formed by some known exact results. By a comparison between the exact expression for the expected delay time and an approximate expected delay time based on the maximum entropy estimate, they argue that their maximum entropy estimate is sufficiently accurate for practical purposes. In this note, we show that their maximum entropy estimate is easily rejected by simulation. We propose a minor modification of their maximum entropy method that significantly improves the quality of the estimate.     

Steady state analysis and computation of the GI/M/1/L queue with multiple working vacations and partial batch rejection

This paper analyzes a finite-buffer bulk-arrival bulk-service queueing system with multiple working vacations and partial batch rejection in which the inter-arrival and service times are, respectively, arbitrarily and exponentially distributed. Using the supplementary variable and the embedded Markov chain techniques, we obtain the waiting queue-length distributions at pre-arrival and arbitrary epochs. We also present Laplace–Stiltjes transform of the actual waiting-time distribution in the queue. Finally, several performance measures and a variety of numerical results in the form of tables and graphs are discussed.     

Analysis of waiting time of M/G/1/K system with vacations under random scheduling and LCFS

This paper considers an M/G/1/K queueing system with multiple vacations under random scheduling and LCFS disciplines. As for M/G/1/K vacation models, Lee obtained the results of the joint distribution of the number of messages in the system and the remaining service or vacation time for a message. Using these expressions, we derive LSTs of the waiting time distribution under the two service disciplines. We show the calculation method for the first and the second moments of the waiting time under two service disciplines. Furthermore, we illustrate some numerical results of the mean waiting times and the coefficient of variations of the waiting time under FCFS, random scheduling and LCFS.     

基于CPN的空竭服务单重休假M/G/1型排队系统建模与分析

空竭服务单重休假M/G/1型排队系统是经典排队系统的推广,在许多领域有着广泛的应用.到目前为止对其的处理方法还都是建立在概率论和数理统计的基础上,运用马尔可夫随机过程求解,推导十分复杂,没有直观的模型描述.因此,利用着色Petri网对空竭服务单重休假M/G/1型排队系统进行建模,并对主要性能指标进行仿真分析是迫切以及可行地.仿真软件选用CPNTools[1],仿真结果证明该方法具有较高的精确度以及实用价值.     

The optimal control of an M/G/1 queueing system with server vacations, startup and breakdowns

This paper studies the control policy of the N policy M/G/1 queue with server vacations, startup and breakdowns, where arrivals form a Poisson process and service times are generally distributed. The server is turned off and takes a vacation whenever the system is empty. If the number of customers waiting in the system at the instant of a vacation completion is less than N, the server will take another vacation. If the server returns from a vacation and finds at least N customers in the system, he requires a startup time before providing service until the system is again empty. It is assumed that the server breaks down according to a Poisson process and his repair time has a general distribution. The system characteristics of such a model are analyzed and the total expected cost function per unit time is developed to determine the optimal threshold of N at a minimum cost.     

A matrix approach for the transient solution of an M/M/1/N queue with discouraged arrivals and reneging

This paper illustrates a computable matrix technique that can be used to derive explicit expressions for the transient state probabilities of a finite waiting space single-server queue, namely (M/M/1/N), having discouraged arrivals and reneging. The discipline is the classical first-come, first-served (FCFS). We obtain the transient solution of the system, with results in terms of the eigenvalues of a symmetric tridiagonal matrix. Finally, numerical calculations are given to illustrate the effectiveness of this technique and system behaviour.     

On Taylor series expansions for waiting times in tandem queues: an algorithm for calculating the coefficients and an investigation of the approximation error

Recently, a Taylor series expansion was developed for expected stationary waiting times in open (max,+)-linear stochastic systems with Poisson input process; these systems cover various instances of queueing networks.As an application, we present an algorithm for calculating the coefficients for infinite capacity tandem queueing networks with discrete service-time distributions. The algorithm works quite efficiently if the random vector of the service times of all servers is concentrated at a small number of atoms. We investigate the relative error of the Taylor approximation by simulation; in many cases, it follows very well a simple expression which holds exactly for independent, exponentially distributed servers.     

The interdeparture time distribution for each class in the ∑Mi/Gi/1 queue with set-up times and repeated server vacations

This paper studies the interdeparture time distribution of one class of customers who arrive at a single server queue where customers of several classes are served and where the server takes a vacation whenever the system becomes empty or is empty when the server returns from a vacation. Furthermore, the first customer in the busy period is allowed to have an exceptional service time (set-up time), depending on the class to which this customer belongs. Batches of customers of each class arrive according to independent Poisson processes and compete with each other on a FIFO basis. All customers who belong to the same class are served according to a common generally distributed service time. Service times, batch sizes and the arrival process are all assumed to be mutually independent. Successive vacation times of the server form independent and identically distributed sequences with a general distribution.For this queueing model we obtain the Laplace transform of the interdeparture time distribution for each class of customers whose batch size is geometrically distributed. No explicit assumptions of the batch size distributions of the other classes of customers are necessary to obtain the results.The paper ends by showing how the mathematical results can be used to evaluate a protocol that controls access to a shared medium of an ATM passive optical network. The numerical results presented in the last section of this paper show that the bundle spacing principle that is used by the permit distribution algorithm of this protocol introduces high delays and in many cases also more variable interdeparture times for the ATM cells of individual connections. An alternative algorithm is proposed that does not cope with these performance short comings and at the same time conserves the good properties of the protocol.