Search

We consider an M X /M/c queue with catastrophes and state-dependent control at idle time. Properties of the queues which terminate when the servers become idle are first studied. Recurrence, equilibrium distribution, and equilibrium queue-size structure are studied for the case of resurrection and no catastrophes. All of these properties and the first effective catastrophe occurrence time are then investigated for the case of resurrection and catastrophes. In particular, we obtain the Laplace transform of the transition probability for the absorbing M X /M/c queue.

This paper presents a novel and computationally efficient methodology for approximating the queue length (the number of customers in the system) distributions of time-varying non-Markovian many-server queues (e.g., Gt/Gt/nt queues), where the number of servers (nt) is large. Our methodology consists of two steps. The first step uses phase-type distributions to approximate the general interarrival and service times, thus generating an approximating Pht/Pht/nt queue. The second step develops strong approximation theory to approximate the Pht/Pht/nt queue with fluid and diffusion limits whose mean and variance can be computed using ordinary differential equations. However, by naively representing the Pht/Pht/nt queue as a Markov process by expanding the state space, we encounter the lingering phenomenoneven when the queue is overloaded. Lingering typically occurs when the mean queue length is equal or near the number of servers, however, in this case it also happens when the queue is overloaded and this time is not of zero measure. As a result, we develop an alternative representation for the queue length process that avoids the lingering problem in the overloaded case, thus allowing for the derivation of a Gaussian diffusion limit. Finally, we compare the effectiveness of our proposed method with discrete event simulation in a variety parameter settings and show that our approximations are very accurate. The online supplement is available at https://doi.org/10.1287/ijoc.2017.0760 .

This paper is concerned with an M/PH/K queue with customer abandonment, constant impatient time, and many servers. By combining the method developed in Choi et al. (Math Oper Res 29:309–325, 2004) and Kim and Kim (Perform Eval 83–84:1–15, 2015) and the state space reduction method introduced in Ramaswami (Stoch Models 1:393–417, 1985), the paper develops an efficient algorithm for computing performance measures for the queueing system of interest. The paper shows a number of properties associated with matrices used in the development of the algorithm, which make it possible for the algorithm, under certain conditions, to handle systems with up to one hundred servers. The paper also obtains analytical properties of performance measures that are useful in gaining insight into the queueing system of interest.

This paper studies a fluid queue driven by a multi-server queue with multiple working vacations and vacation interruption. The stationary distribution of the background environment is obtained after some manipulation. A system of differential equations satisfied by the fluid queue is presented, by which we gain the matrix-geometric structure of the Laplace transform of the stationary buffer content. Furthermore, we derive the explicit expression of the mean buffer content. Finally, the numerical example is employed to illustrate our results.

We consider an infinite-server queue, where the arrival and service rates are both governed by a continuous-time Markov chain that is independent of all other aspects of the queue. Through constructing a pretty Markov process, several performance measures are derived by using the supplementary variable technique. In addition, special cases and numerical examples are studied in detail.

We offer a new profit-maximizing mechanism for Naor’s M/M/1 model, and bound the loss incurred when the waiting room’s size is limited or the server is restricted to a static price and FCFS discipline.

The B M A P ∕ S M ∕ 1 queue is the most general single-server queueing model which can be analysed analytically. Problem of computation of stationary distributions of queue length is solved in the literature. However, the problem of computation of the moments of these distributions is not enough addressed. This problem is more complicated than its particular case when the service times are independent identically distributed random variables due to reducibility of some involved matrices. In this communication, we solve this problem.

We propose a vacation queue model for a signalized traffic intersection to elucidate intra-cycle queue size variations. Each incoming street to the intersection is modeled to experience Poisson arrivals, and to have finite queue capacity; vehicles arriving to full queue are dropped. Under a fixed-time policy, the queue size dynamics on each street are decoupled. Motivated by vacation queues, an imbedded Markov chain corresponding to queue sizes at the end of cycles is considered, whose transition probabilities are computed from analytical transient solutions of M/D/1/N queues. Sufficient conditions for convergence to steady-state distributions are provided for fixed-time policy. Simulations suggest consistency between the queue sizes computed by the proposed model, and the Webster and time-dependent traffic queue models.

In this paper, we study the steady state behaviour of an M/G/1 queue with two types of general heterogeneous service and optional repeated service subject to server’s breakdowns occurring randomly ...

A queueing system (QS) with finite size holds a current number N, and maximum number M, of present customers (waiting or being served), N ∊ {0, 1, … , M}. We model the system as family of Birth–Death Processes in equilibrium, with size M + 1, indexed by the system utilization parameter. Depending on the concepts of information i and entropy S = E(i) of QS, we promote an information analysis of queueing systems. Introducing the information stiffness of QS, the system information (entropy) consists of three basic parts: null, elastic (Hooke’s), and synchronization part. A QS can function in information elastic, antielastic, or inelastic regime. We use the coefficients of information elasticity and of unpredictability to determine the optimal arrival/service mode of customers. This analysis is illustrated on the information linear (i.e. M/M/1/M and M/M/1), harmonically encouraged arrivals (or discouraged service), and M/M/1/M/M type QS. Also, short remarks are given for the Erlang loss, Poisson, and ...

We study a system of two non-identical and separate M/M/1/• queues with capacities (buffers) C1 < ∞ and C2 = ∞, respectively, served by a single server that alternates between the queues. The server’s switching policy is threshold-based, and, in contrast to other threshold models, is determined by the state of the queue that is not being served. That is, when neither queue is empty while the server attends Qi (i = 1, 2), the server switches to the other queue as soon as the latter reaches its threshold. When a served queue becomes empty we consider two switching scenarios: (i) Work-Conserving, and (ii) Non-Work-Conserving. We analyze the two scenarios using Matrix Geometric methods and obtain explicitly the rate matrix R, where its entries are given in terms of the roots of the determinants of two underlying matrices. Numerical examples are presented and extreme cases are investigated.

The paper considers retrial queueing system M /M /1/ 0 with combined service discipline, namely, a customer from the orbit is serviced in its turn, but in case of a free channel an arrival from the original flow is serviced immediately. The author obtains the expressions for state probabilities as well as ergodicity conditions. The system is compared with the Lakatos-type system.

This paper is concerned with a discrete-time Geo/G/1 repairable queueing system with Bernoulli feedback and randomized p,N-policy. The service station may be subject to failures randomly during serving customers and therefore is sent for repair immediately. The p,N-policy means that when the number of customers in the system reaches a given threshold value N, the deactivated server is turned on with probability p or is still left off with probability 1−p. Applying the law of total probability decomposition, the renewal theory and the probability generating function technique, we investigate the queueing performance measures and reliability indices simultaneously in our work. Both the transient queue length distribution and the recursive expressions of the steady-state queue length distribution at various epochs are explicitly derived. Meanwhile, the stochastic decomposition property is presented for the proposed model. Various reliability indices, including the transient and the steady-state unavailability of the service station, the expected number of the service station breakdowns during the time interval 0+,n+ and the equilibrium failure frequency of the service station are also discussed. Finally, an operating cost function is formulated, and the direct search method is employed to numerically find the optimum value of N for minimizing the system cost. Copyright © 2017 John Wiley & Sons, Ltd.

In this paper, a single server queue with variable batch size service, Poisson bulk arrival with multiple working vacations and server breakdown is considered. In working vacation, the server works with different rates rather than completely stoping the service during the vacation period. In this model, during the working vacation the server starts the service if it finds at least one customer in the queue with a maximum of ‘b’ customers, otherwise the server serves with variable batch size. Service time in working vacation and in regular period follows general distribution. The probability generating function of a queue size at an arbitrary time epoch as well as other completion epochs is derived. Expected queue length in a steady state is obtained. Also a numerical illustration is presented.

In this paper, analysis of single queue, multi-server with limited system capacity under first come first served discipline was carried out using iterative method. The arrivals of customers and service times of customers are assumed poisson and exponential distributions respectively. This queuing model is an extension of single queue, single server with limited system capacity. Performance measures of the model, such as the expected number of customers in the queue and in the system, the expected waiting times of customers in the queue and in the system respectively were derived. The performance measures so derived were compared with that of single queue, single server with limited capacity {M/M/1:(N/FCFS)} model. The numerical illustration indicates that single queue, multi-server with limited capacity {M/M/c:(N/FCFS)} model is more effective and efficient in handling congestions.Keywords: Iterative method, Single queue, Multi-Server queue model, Limited capacity, Performance measures

This paper considers an infinite-buffer batch-service queue with Markovian arrival process, generally distributed and batch-size-dependent service time. We obtain a bivariate vector generating function of queue length and server content distribution at departure epoch of a batch. The complete joint distribution of queue length, server content and phase of the arrival process at departure epoch is extracted in terms of roots of the associated characteristic equation. By employing these probability vectors we also perceive the joint distribution at arbitrary and pre-arrival epochs. Our analytic procedure and results are demonstrated using some numerical examples for phase-type as well as deterministic service time distributions with high and low values of model parameters. The occurrence of multiple roots are also investigated in case of phase-type service time distribution. Finally, we also investigate the influence of correlation of the arrival process on the behavior of the system performance.

In this paper, we propose a numerical method, based on Taylor series expansion, for computing the uncertainty in performance measures of vacation queueing model due to epistemic uncertainties in its parameters. Specifically, we consider the M/G/1/N queue with vacations, where we assume that vacation parameter is derived from finite number of observations, they themselves will have epistemic uncertainty associated with them. Using this method, we compute the expected value and the variance of the stationary distribution associated with the M/G/1/N queue with vacations. In order to illustrate the applicability of the proposed method, a series of numerical examples are discussed and the obtained results are compared to the corresponding Monte Carlo simulations ones.

We consider a finite-buffer single-server queue with batch Markovian arrival process. In the case of finite-buffer batch arrival queue, there are different customer rejection/acceptance strategies such as partial batch rejection, total batch rejection, and total batch acceptance policy. We consider partial batch rejection strategy throughout our paper. We obtain queue length distributions at various epochs such as pre-arrival, arbitrary, and post-departure as well as some important performance measures, like probability of loss for the first, an arbitrary, and the last customer of a batch, mean queue lengths, and mean waiting times. The corresponding queueing model under single and multiple vacation policy has also been investigated. Some numerical results have been presented in the form of tables by considering phase-type and Pareto service time distributions. The proposed analysis is based on the successive substitutions in the Markov chain equations of the queue-length distribution at an embedded post-departure epoch of a customer. We also establish relationships among the queue-length distributions at post-departure, arbitrary, and pre-arrival epochs using the classical argument based on Markov renewal theory and semi-Markov processes. Such queueing systems find applications in the performance evaluation of teletraffic part in 4G A11-IP networks.

We present an analysis of the queueing system in which arriving jobs are dropped with probability depending on the queue size. The arrivals are assumed to be autocorrelated and they are modeled by the Markov-modulated Poisson process. Both transient and stationary distributions of the queue size, as well as the system loss ratio and throughput are obtained. The analytical results are accompanied with numerical examples based on the autocorrelated traffic recorded in an IP computer network.

This paper is concerned with a discrete-time Geo /G / 1 queueing system with D -policy and J -optional services in which the service station may be subject to failures at random during serving the customers. All the arriving customers require the first essential service, whereas some of them may opt for a second service from the J additional services with some probability. As soon as the system becomes empty, the server will not restart the service until the sum of the service times of the waiting customers in the system reaches or exceeds some given positive integer D . Applying the total probability decomposition law, renewal theory, and probability generating function technique, the queueing indices and reliability measures are investigated simultaneously in our work. Both the probability generating function of the transient queue length distribution and the explicit formulas of the steady-state queue length distribution at time epoch n + are derived. Meanwhile, the stochastic decomposition property is presented for the proposed model. Various reliability indices, including the transient and steady-state unavailability, the expected number of breakdowns during (0+ ,n + ], and the equilibrium failure frequency, are discussed. Finally, the optimum value of D for minimizing the system cost is numerically discussed under a given cost structure.

A queueing system of the M/G/n-type, n ≥ 1, with a bounded total volume is considered. It is assumed that the volumes of the arriving packets are generally distributed random variables. Moreover, the AQM-type mechanism is used to control the actual buffer state: each of the arriving packets is dropped with a probability depending on its volume and the occupied volume of the system at the pre-arrival epoch. The explicit formulae for the stationary queue-size distribution and the loss probability are found. Numerical examples illustrating theoretical formulae are given as well.

This work suggests a new analysis approach for a discrete-time GI/G/1 queue with multiple vacations. The method used is called a modified supplementary variable technique and our result is an exact transform-free expression for the steady state queue length distribution. Utilizing this result, we propose a simple two-moment approximation for the queue length distribution. From this, approximations for the mean queue length and the probabilities of the number of customers in the system are also obtained. To evaluate the approximations, we conduct numerical experiments which show that our approximations are remarkably simple yet provide fairly good performance, especially for a Bernoulli arrival process.

This paper investigates the M/M/s queueing model to predict an estimate for the proximity of the performance measures of queues with arrival processes that are slightly different from the Poisson process. Specifically, we use the strong stability method to obtain perturbation bounds on the effect of perturbing the arrival process in the M/M/s queue. Therefore, we build some algorithms based on strong stability method to predict stationary performance measures of the GI/M/s queue. Some numerical examples are sketched out to illustrate the accuracy of the proposed method.

This article develops a computational algorithm for the loss probability in the stationary M/G/1 queue with impatient customers whose impatience times follow a phase-type distribution (M/G/1+PH). T...

Time-dependent solutions to queuing models are very useful for evaluating the performance of real-world systems. However, because of their mathematical complexity, few available results exist. In this paper, we derive the time-dependent performance measures for an M / D / 1 queue starting with a positive number of initial customers. Using the limiting property of an Erlang distribution, we obtain closed-form time-dependent formulas for the queue length and the waiting time. Furthermore, the time-dependent queue length probability in a busy period is derived.

We establish a limit theorem supporting a Poisson approximation for the departure process from a multi-server queue that tends to have many busy servers. This limit can support approximating a flow out of such a queue in a complex queueing network by an independent Poisson source. The main ideas are: (i) to scale time so that previous many-server heavy-traffic limits can be applied and (ii) for time-varying arrival-rate functions, to scale (spread out) time by a large factor about each fixed time.

This paper studies a fluid queueing model driven by an M / M / 1 queue subject to working vacation. The underlying system of differential difference equations that governs the process is solved using continued fraction and generating function methodologies. Explicit expressions for the joint steady-state probabilities of the state of the background queueing model and the content of the buffer are obtained in terms of modified Bessel function of the first kind. Numerical illustrations are added to depict the variations of the state probabilities and the buffer content distributions against varying values of the parameters subject to the stability conditions.

A single-channel queueing system with an Erlang incoming flow and random server unavailability intervals as the system releases is considered. The nonstationary and stationary distributions of queue length are obtained.

We introduce the EP queue -- a significant generalization of the M B / G /1 queue that has state-dependent service time probability distributions and incorporates power-up for first arrivals and power-down for idle periods. We derive exact results for the busy-time and response-time distributions. From these, we derive power consumption metrics during nonidle periods and overall response time metrics, which together provide a single measure of the trade-off between energy and performance. We illustrate these trade-offs for some policies and show how numerical results can provide insights into system behavior. The EP queue has application to storage systems, especially hard disks, and other data-center components such as compute servers, networking, and even hyperconverged infrastructure.

This paper considers a discrete-time Geo/G/1 queue under the Min(N,D)-policy in which the idle server resumes its service if either N customers accumulate in the system or the total backlog of the service times of the waiting customers exceeds D, whichever occurs first (Min(N,D)-policy). By using renewal process theory and total probability decomposition technique, the authors study the transient and equilibrium properties of the queue length from the beginning of the arbitrary initial state, and obtain both the recursive expression of the z-transformation of the transient queue length distribution and the recursive formula for calculating the steady state queue length at arbitrary time epoch n +. Meanwhile, the authors obtain the explicit expressions of the additional queue length distribution. Furthermore, the important relations between the steady state queue length distributions at different time epochs n -, n and n + are also reported. Finally, the authors give numerical examples to illustrate the effect of system parameters on the steady state queue length distribution, and also show from numerical results that the expressions of the steady state queue length distribution is important in the system capacity design.

This paper studies a finite buffer size Geo X / G / 1 / N queue with single working vacation and different input rates. By combining two classic methods of supplementary variable and embedded Markov chain, the matrix-form solutions of queue-length distributions at departure, arbitrary, pre-arrival and outside observer's observation epochs are obtained. Based on these queue-length distributions, some performance measures are also derived and some numerical experiments are carried out. Then, an optimal control on state-dependent operating cost of a production to order is presented. HighlightsAnalyze a new queue model raised from practical production system.Obtain the solutions in form of formulae for queue length distributions at different epochs.Optimal analysis for the state-dependent cost of system.

This paper explores a discrete-time Geo / G / 1 queueing system with N-policy and D-policy wherein customers arrive at the system in variable input rates according to the states of the server. When the system becomes empty, the server stays idle until the number of waiting customers reaches N or the sum of the service times of the waiting customers in the system reaches or exceeds a predetermined positive integer D, whichever happens first (referred to as Min(N, D)-policy). Employing the renewal theory, the total probability decomposition law and the probability generating function technique we obtain the probability generating function for the transient queue size distribution at time epoch $$n^+$$ . Also, the explicit recursive formulas of the steady-state queue length distribution at time epochs $$n^+$$ , n, $$n^-$$ and outside observer’s time epoch are derived, respectively. Finally, some numerical experiments are conducted to investigate the sensitivity of system performance measures and the optimization of system capacity.

An elegant and simple solution to determine the distributions of queue length at different epochs and the waiting time for the model $$GI^{X}/M/c$$GIX/M/c is presented. In the past, the model $$GI^{X}/M/c$$GIX/M/c has been extensively analyzed using various techniques by many authors. The purpose of this paper is to present a simple and effective derivation of the analytic solution for pre-arrival epoch probabilities as a linear combination of specific geometric terms (except for the boundary probabilities when the number of servers is greater than the maximum batch size) involving the roots of the underlying characteristic equation. The solution is then leveraged to compute the waiting-time distributions of both first and arbitrary customers of an incoming batch. Numerical examples with various arrival patterns and batch size distributions are also presented. The method that is being proposed here not only gives an alternate solution to the existing methods, but it is also analytically simple, easy to implement, and computationally efficient. It is hoped that the results obtained will prove beneficial to both theoreticians and practitioners.

In this paper, a priority polling system consisting of three M / M / 1 queues, served by a single server is investigated. Queue 1 has the Head-of-Line (HoL) priority and Queue 2 has a higher priority over Queue 3 with threshold N. All the switches are instantaneous and preempting. Using the Kernel method we derive the probability of generating functions of the stationary joint queue-length distributions, which yields the mean queue lengths and the mean sojourn times. Furthermore, we consider the limit behaviors in the light-traffic and heavy-traffic scenarios. And an interpolation approximation for the sojourn times utilizing the light and heavy traffic limits are illustrated. To test the validity, we also undertake some simulation works.

This paper deals with the stationary analysis of a fluid queue driven by anM/M/1queueing model subject to Bernoulli-Schedule-Controlled Vacation and Vacation Interruption. The model under consideration can be viewed as a quasi-birth and death process. The governing system of differential difference equations is solved using matrix-geometric method in the Laplacian domain. The resulting solutions are then inverted to obtain an explicit expression for the joint steady state probabilities of the content of the buffer and the state of the background queueing model. Numerical illustrations are added to depict the convergence of the stationary buffer content distribution to one subject to suitable stability conditions.

In this work, we are interested in the approximation of the stationary characteristics of the GI/M/∞ system by those of an M/M/∞ system. In other words, we propose to study the strong stability of the M/M/∞ system (ideal system) when the arrivals flow is subject to a small perturbation (the GI/M/∞ is the resulting perturbed system). For this purpose, we first determine the approximation conditions of the characteristics of the perturbed queuing system, and under these conditions we obtain the stability inequalities of the stationary distribution of the queue size. To evaluate the performance of the proposed method, we develop an algorithm which allows us to compute the various theoretical results and which is executed on some systems (Coxian2/M/∞ and E2/M/∞) in order to compare its output results with those of simulation.

In this paper we consider an M/M/c queue modified to allow both mass arrivals when the system is empty and the workload to be removed. Properties of queues which terminate when the server becomes idle are firstly developed. Recurrence properties, equilibrium distribution, and equilibrium queue-size structure are studied for the case of resurrection and no mass exodus. All of these results are then generalized to allow for the removal of the entire workload. In particular, we obtain the Laplace transformation of the transition probability for the absorptive M/M/c queue.

A single server Markovian queueing model is considered. The arrivals are allowed to join the queue according to a Poisson distribution and the service takes place according to an exponential distribution. Whenever the system is empty, the server goes for a vacation and return back to the system after N or more customers are found in the system. If the number of customers in the system is less than ‘’ then the server takes another vacation. In this paper, we obtain explicit expressions for the time dependent system size probabilities of such a model using Laplace transform and generating function techniques. Numerical illustrations are added to support the theoretical results obtained.

We consider the loss probability P loss in the stationary M/G/1 queue with generally distributed impatience times (M/G/1+G queue). Recently, it was shown that P loss increases with service times in the convex order. In this paper, we show that P loss also increases with impatience times in the excess wealth order. With these results, we show that P loss in the M/D/1+D queue is smallest among all M/G/1+G queues with the same and finite arrival rate, mean service time, and mean impatience time.

This paper studies an M/G/1 queue in a multi-phase random environment. When in operative phase i, i=1,2,…,n, the system is subject to disastrous interruptions, causing all present customers (waiting and served) to leave the system. At an exponential failure instant, the server abandons the service and the system goes directly to repair phase. After an exponential repair time, the system moves to operative phase i with probability qi, i=1,2,…,n. Using the supplementary variable technique, we obtain the distribution for the stationary queue at an arbitrary epoch. We also derive results of the cycle analysis, the sojourn time distribution and the length of the server's working time in a service cycle. In addition, some special cases and numerical examples are presented.

In this paper we consider the MMAP/PH/1 priority queue, both the case of preemptive resume and the case of non-preemptive service. The main idea of the presented analysis procedure is that the sojourn time of the low priority jobs in the preemptive case (and the waiting time distribution in the non-preemptive case) can be represented by the duration of the busy period of a special Markovian fluid model. By making use of the recent results on the busy period analysis of Markovian fluid models it is possible to calculate several queueing performance measures in an efficient way including the sojourn time distribution (both in the time domain and in the Laplace transform domain), the moments of the sojourn time, the generating function of the queue length, the queue length moments and the queue length probabilities.

A queueing system with 2 parallel workstations is common in the field. Typically, the workstations have different features in terms of the inter arrival times of customers and the service times for the customers. Computer simulation study on the optimal server allocation for parallel heterogeneous queueing systems with fixed number of identical servers is presented in this paper. The queueing system is optimized with respect to minimizing the weighted system time of the customers served by 2 parallel workstations. The system time formula for the M/M/c systems in Kendall’s notation is known. Thus, we first compute the optimal allocation for parallel M/M/c systems, comparing the results with those from the computer simulation experiments, and have the same results. The CETI rule is devised through optimizing M/M/c cases, which allocates the servers based on Close or Equal Traffic Intensities between workstations. Traffic intensity is defined as the arrival rate divided by the service rate times the number of servers. The CETI rule is shown to work for M/G/c, G/M/c queueing systems by numerous computer simulation experiments, even if the rule cannot be proven analytically. However, the CETI rule is shown not to work for some of G/G/c systems.

We analyze an M/G/1/K queueing system with queue-length dependent service and arrival rates. There are a single server and a buffer with finite capacity K including a customer in service. The customers are served by a first-come-first-service basis. We put two thresholds and ( ) on the buffer. If the queue length at the service initiation epoch is less than the threshold , the service time of customers follows with a mean of and the arrival of customers follows a Poisson process with a rate of . When the queue length at the service initiation epoch is equal to or greater than and less than , the service time is changed to with a mean of . The arrival rate is still . Finally, if the queue length at the service initiation epoch is greater than , the arrival rate of customers are also changed to a value of and the mean of the service times is . By using the embedded Markov chain method, we derive queue length distribution at departure epochs. We also obtain the queue length distribution at an arbitrary time by the supplementary variable method. Finally, performance measures such as loss probability and mean waiting time are presented.

This article considers a finite-source queueing model of M/G/1 type in which a customer, arriving at a moment of a busy server, is not allowed either to queue or to do repetitions. Instead, for an exponentially distributed time interval he is blocked in the orbit of inactive customers. We carry out a steady state analysis of the system and compare it with the corresponding system with retrials. Optimization problems are considered and formulas for the Laplace–Stieltjes transform of the busy period length are obtained.