On multiserver feedback retrial queue with finite buffer

This paper deals with a multiserver feedback retrial queueing system with finite waiting position and constant retrial rate. This system is analyzed as a quasi-birth-and-death (QBD) process and the necessary and sufficient condition for stability of the system is investigated. Some important system performance measures are obtained using matrix geometric method. The effect of various parameters on the system performance measures are illustrated numerically. Finally, the algorithmic development of the full busy period for the model under consideration is discussed.     

A matrix continued fraction approach to multiserver retrial queues

We consider basic M/M/c/c (c≥1) retrial queues where the number of busy servers and that of customers in the orbit form a level-dependent quasi-birth-and-death (QBD) process with a special structure. Based on this structure and a matrix continued fraction approach, we develop an efficient algorithm to compute the joint stationary distribution of the numbers of busy servers and retrial customers. Through numerical experiments, we demonstrate that our algorithm works well even for M/M/c/c retrial queues with large value of c.     

On the discrete-time system with server breakdowns: Computational algorithm and optimization algorithm

This paper analyzes a discrete-time Geo/Geo/1 queueing system with the server subject to breakdowns and repairs, in which two different possible types of the server breakdowns are considered. In Type 1, the server may break down only when the system is busy, while in Type 2, the server can break down even if the system is idle. The server lifetimes are assumed to be geometrical and the server repair times are also geometric distributions. We model this system by the level-dependent quasi-birth-death (QBD) process and develop computation algorithms of the stationary distribution of the number of customers in the system using the matrix analytic method. The search algorithm for parameter optimization based on a cost model is developed and performed herein.     

A fuzzy based threshold policy for a single server retrial queue with vacations

In this paper we deal with a single server retrial queue with vacations. The server serves the customers until the system becomes empty, then it takes a vacation. The system consists of two types of costs. The blocking cost is considered whenever a customer is blocked either because of the server is busy or off. There is also a cost each time the server is turned on. The problem is to find an effective policy for turning on the dormant server. We propose a Fuzzy Based Threshold Policy (FBTP) to control the server, substitute for conventional threshold policies. The FBTP is based on four input parameters, an inference stage and it is tuned up using a stochastic List Based Threshold Accepting (LBTA) algorithm. Simulation models are developed to validate the fuzzy controller. Numerical experiments are provided to show that the proposed method is superior to crisp threshold policies.     

Quasi-birth-and-death Markov processes with a tree structure and the MMAP[K]/PH[K]/N/LCFS non-preemptive queue

This paper studies a multi-server queueing system with multiple types of customers and last-come-first-served (LCFS) non-preemptive service discipline. First, a quasi-birth-and-death (QBD) Markov process with a tree structure is defined and some classical results of QBD Markov processes are generalized. Second, the MMAP[K]/PH[K]/N/LCFS non-preemptive queue is introduced. Using results of the QBD Markov process with a tree structure, explicit formulas are derived and an efficient algorithm is developed for computing the stationary distribution of queue strings. Numerical examples are presented to show the impact of the correlation and the pattern of the arrival process on the queueing process of each type of customer.     

A Newton-type univariate optimization algorithm for locating the nearest extremum

This paper introduces an algorithm for univariate optimization using linear lower bounding functions (LLBF's). An LLBF over an interval is a linear function which lies below the given function over an interval and matches the given function at one end point of the interval. We first present an algorithm using LLBF's for finding the nearest root of a function in a search direction. When the root-finding method is applied to the derivative of an objective function, it is an optimization algorithm which guarantees to locate the nearest extremum along a search direction. For univariate optimization, we show that this approach is a Newton-type method, which is globally convergent with superlinear convergence rate. The applications of this algorithm to global optimization and other optimization problems are also discussed.     

Retrial queues with balanced call blending: analysis of single-server and multiserver model

In call centers, call blending consists in the mixing of incoming and outgoing call activity, according to some call blending balance. Recently, Artalejo and Phung-Duc have developed an apt model for such a setting, with a two way communication retrial queue. However, by assuming a classical (proportional) retrial rate for the incoming calls, the short-term blending balance is heavily impacted by the number of incoming calls, which may be undesired, especially when the balance between incoming and outgoing calls is vital to the service offered. In this contribution, we consider an alternative to classical call blending, through a retrial queue with constant retrial rate for incoming calls. For the single-server case (one operator), a generating functions approach enables to derive explicit formulas for the joint stationary distribution of the number of incoming calls and the system state, and also for the factorial moments. This is complemented with a stability analysis, expressions for performance measures, and also recursive formulas, allowing reliable numerical calculation. A correlation study enables to study the system’s short-term blending balance, allowing to compare it to that of the system with classical retrial rate. For the multiserver case (multiple operators), we provide a quasi-birth-and-death process formulation, enabling to derive a sufficient and necessary condition for stability in this case (in a simple form), a numerical recipe to obtain the stationary distribution, and a cost model.     

Phase-type models for cellular networks supporting voice, video and data traffic

This paper presents an analytical model for cellular networks supporting voice, video and data traffic. Self-similar and bursty nature of the incoming traffic causes correlation in inter-arrival times of the incoming traffic. Therefore, arrival of calls is modeled with Markovian arrival process as it allows for the correlation. Call holding times, cell residence times and retrial times are modeled as phase-type distributions. We consider that the cells in a cellular network are statistically homogeneous, so it is enough to investigate a single cell for the performance analysis of the entire networks. With appropriate assumptions, the stochastic process that describes the state of a cell is a Quasi-birth–death (QBD) process. We derive explicit expressions for the infinitesimal generator matrix of this QBD process. Also, expressions for performance measures are obtained. Further, complexity involved in computing the steady-state probabilities is discussed. Finally, queueing examples are provided that can be obtained as particular cases of the proposed analytical model.     

The m/g/1 retrial queue with nonpersistent customers

We consider anM/G/1 retrial queue in which blocked customers may leave the system forever without service. Basic equations concerning the system in steady state are established in terms of generating functions. An indirect method (the method of moments) is applied to solve the basic equations and expressions for related factorial moments, steady-state probabilities and other system performance measures are derived in terms of server utilization. A numerical algorithm is then developed for the calculation of the server utilization and some numerical results are presented.     

An <Emphasis Type="Italic">M</Emphasis><Superscript>[<Emphasis Type="Italic">X</Emphasis>]</Superscript>/<Emphasis Type="Italic">G</Emphasis>/1 retrial queue with server breakdowns and constant rate of repeated attempts

We consider an M ^[X]/G/1 retrial queue subject to breakdowns where the retrial time is exponential and independent of the number of customers applying for service. If a coming batch of customers finds the server idle, one of the arriving customers begins his service immediately and the rest joins a retrial group (called orbit) to repeat his request later; otherwise, if the server is busy or down, all customers of the coming batch enter the orbit. It is assumed that the server has a constant failure rate and arbitrary repair time distribution. We study the ergodicity of the embedded Markov chain, its stationary distribution and the joint distribution of the server state and the orbit size in steady-state. The orbit and system size distributions are obtained as well as some performance measures of the system. The stochastic decomposition property and the asymptotic behavior under high rate of retrials are discussed. We also analyse some reliability problems, the k-busy period and the ordinary busy period of our retrial queue. Besides, we give a recursive scheme to compute the distribution of the number of served customers during the k-busy period and the ordinary busy period. The effects of several parameters on the system are analysed numerically. I. Atencia’s and Moreno’s research is supported by the MEC through the project MTM2005-01248.     

Geo/Geo/1 retrial queue with non-persistent customers and working vacations

In this paper, we consider a Geo/Geo/1 retrial queue with non-persistent customers and working vacations. The server works at a lower service rate in a working vacation period. Assume that the customers waiting in the orbit request for service with a constant retrial rate, if the arriving retrial customer finds the server busy, the customer will go back to the orbit with probability q (0≤q≤1), or depart from the system immediately with probability $\bar{q}=1-q$ . Based on the necessary and sufficient condition for the system to be stable, we develop the recursive formulae for the stationary distribution by using matrix-geometric solution method. Furthermore, some performance measures of the system are calculated and an average cost function is also given. We finally illustrate the effect of the parameters on the performance measures by some numerical examples.     

Ergodicity of the BMAP/PH/s/s+K retrial queue with PH-retrial times

Define the traffic intensity as the ratio of the arrival rate to the service rate. This paper shows that the BMAP/PH/s/s+K retrial queue with PH-retrial times is ergodic if and only if its traffic intensity is less than one. The result implies that the BMAP/PH/s/s+K retrial queue with PH-retrial times and the corresponding BMAP/PH/s queue have the same condition for ergodicity, a fact which has been believed for a long time without rigorous proof. This paper also shows that the same condition is necessary and sufficient for two modified retrial queueing systems to be ergodic. In addition, conditions for ergodicity of two BMAP/PH/s/s+K retrial queues with PH-retrial times and impatient customers are obtained. This revised version was published online in June 2006 with corrections to the Cover Date.     

Rate control for communication networks: shadow prices,proportional fairness and stability

This paper analyses the stability and fairness of two classes of rate control algorithm for communication networks. The algorithms provide natural generalisations to large-scale networks of simple additive increase/multiplicative decrease schemes, and are shown to be stable about a system optimum characterised by a proportional fairness criterion. Stability is established by showing that, with an appropriate formulation of the overall optimisation problem, the network's implicit objective function provides a Lyapunov function for the dynamical system defined by the rate control algorithm. The network's optimisation problem may be cast in primal or dual form: this leads naturally to two classes of algorithm, which may be interpreted in terms of either congestion indication feedback signals or explicit rates based on shadow prices. Both classes of algorithm may be generalised to include routing control, and provide natural implementations of proportionally fair pricing.     

A New Method for Finding the Characteristic Roots of E<Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>/E<Subscript><Emphasis Type="Italic">m</Emphasis></Subscript>/1 Queues

In 1953, Smith (Proc Camb Philos Soc 49:449–461, 1953), and, following him, Syski (1960) suggested a method to find the waiting time distribution for one server queues with Erlang-n arrivals and Erlang-m service times by using characteristic roots. Syski shows that these roots can be determined from a very simple equation, but an equation of degree n + m. Syski also shows that almost all of the characteristic roots are complex. In this paper, we derive a set of equations, one for each complex root, which can be solved by Newton’s method using real arithmetic. This method simplifies the programming logic because it avoids deflation and the subsequent polishing of the roots. Using the waiting time distribution, Syski then derived the distribution of the number in the system after a departure. E _n /E _m /1 queues can also formulated as quasi birth-death (QBD) processes, and in this case, the characteristic roots discussed by Syski are closely related to the eigenvalues of the QBD process. The QBD process provides information about the number in system at random times, but they are much more difficult to formulate and solve.     

Supply chain model for a deteriorating product with time-varying demand and production rate

The paper develops a two-echelon supply chain model with a single-buyer and a single-vendor. The buyer sells a seasonal product over a short selling period and its inventory is subject to deterioration at a constant rate over time. The vendor's production rate is dependent on the buyer's demand rate, which is a linear function of time. Also, the vendor's production process is not perfectly reliable; it may shift from an in-control state to an out-of-control state at any time during a production run and produce some defective (non-conforming) items. Assuming that the vendor follows a lot-for-lot policy for replenishment made to the buyer, the average total cost of the supply chain is derived and an algorithm for finding the optimal solution is developed. The numerical study shows that the supply chain coordination policy is more beneficial than those policies obtained separately from the buyer's and the vendor's perspectives.     

A G/M/1 retrial queue with constant retrial rate

In this paper, we are concerned with the analytical treatment of an GI/M/1 retrial queue with constant retrial rate. Constant retrial rate is typical for some real world systems where the intensity of individual retrials is inversely proportional to the number of customers in the orbit or only one customer from the orbit is allowed to make the retrials. In our model, a customer who finds the server busy joins the queue in the orbit in accordance with the FCFS (first-come-first-out) discipline and only the oldest customer in the queue is allowed to make the repeated attempts to reach the server. A distinguishing feature of the considered system is an arbitrary distribution of inter-arrival times, while the overwhelming majority of the papers is devoted to the retrial systems with the stationary Poisson arrival process. We carry out an extensive analytical analysis of the queue in steady state using the well-known matrix analytic technique. The ergodicity condition and simple expressions for the stationary distributions of the system states at pre-arrival, post-arrival and arbitrary times are derived. The important and difficult problem of finding the stationary distribution of the sojourn time is solved in terms of the Laplace–Stieltjes transform. Little’s formula is proved. Numerical illustrations are presented.     

A heuristic algorithm for the optimization of a retrial system with Bernoulli vacation

In this study, we consider an M/M/c retrial queue with Bernoulli vacation under a single vacation policy. When an arrived customer finds a free server, the customer receives the service immediately; otherwise the customer would enter into an orbit. After the server completes the service, the server may go on a vacation or become idle (waiting for the next arriving, retrying customer). The retrial system is analysed as a quasi-birth-and-death process. The sufficient and necessary condition of system equilibrium is obtained. The formulae for computing the rate matrix and stationary probabilities are derived. The explicit close forms for system performance measures are developed. A cost model is constructed to determine the optimal values of the number of servers, service rate, and vacation rate for minimizing the total expected cost per unit time. Numerical examples are given to demonstrate this optimization approach. The effects of various parameters in the cost model on system performance are investigated.     

Seeking optimum project duration extensions

It is well-known that changes to a project's definition during the course of the project can cause significant disruption, and greatly extend a project's duration if no extra resources are committed to the project. However, it is also well-known that the opposite policy, of throwing as many resources as possible at the problem to try to keep to the original schedule, can be very expensive, and is often in fact counter-productive ($2000 hour). The underlying causes of the results for these two extreme policies are systemic, are often hard to quantify, and are often significantly under-estimated. This paper describes the system dynamics technique for modelling a project, using as a case-study a model drawn up for a delay and disruption claim; this model closely reflected the project both as budgetted and as actually occured. It then shows how this model could be used to find an optimum trade-off between the two extreme policies, giving an optimal project extension.