Search

This paper deals with a single-server discrete-time Geo/G/1 queueing model with Bernoulli feedback and N-policy where the server leaves for modified multiple vacations once the system becomes empty. Applying the law of probability decomposition, the renewal theory and the probability generating function technique, we explicitly derive the transient queue length distribution as well as the recursive expressions of the steady-state queue length distribution. Especially, some corresponding results under special cases are directly obtained. Furthermore, some numerical results are provided for illustrative purposes. Finally, a cost optimization problem is numerically analyzed under a given cost structure.

Queueing optimization is a science currently gaining importance in view of its contribution to operations research and marketing management. Capacity of the queue, service policy followed and the job flow into the system are the key variables which affect the cost efficiency of a system. In this proposed model we use Kingman relation to optimize M/G/k queue where the servers returns to function only if there are L jobs and also L is less than k. An expression for the expected cost for one execution cycle per unit time and the average time required for the execution of one cycle is obtained. The average cost incurred per unit time is also obtained.

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.

By observing the points only when the queue size changes, we study the PH/PH/k system with heterogeneous servers. We develop Markov chain set ups that are more efficient than studying the systems at arbitrary times, by reducing the sizes of matrices that need to be computed. Specifically we present procedures for constructing the associated Markov chains so one may use matrix-analytic methods for their analysis. This work is carried out for both the continuous and discrete time cases.

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.

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.

A repair facility consisting of one repairman and two arrival streams of failed items, from bases 1 and 2 is considered. The arrival processes are independent Poisson processes, and the repair times are independent and identically exponentially distributed. The item types are exchangeable in the sense that a customer leaves the system with a fixed item, not necessarily the item he has brought. The rule according to which backorders are satisfied by repaired items is the longest queue rule: at the completion of a service (repair), the repaired item is delivered to the base that has the largest number of failed items. We obtain simple expressions for the marginal queue length distributions and for the probability mass function of the difference between the queue lengths. Finally we derive a recursive expression for the Laplace transform of the customer’s sojourn time in system, given the length of the queue at the arrival time point.

We consider a model consisting of two fluid queues driven by the same background continuous-time Markov chain, such that the rates of change of the fluid in the second queue depend on whether the first queue is empty or not: when the first queue is nonempty, the content of the second queue increases, and when the first queue is empty, the content of the second queue decreases. We analyze the stationary distribution of this tandem model using operator-analytic methods. The various densities (or Laplace–Stieltjes transforms thereof) and probability masses involved in this stationary distribution are expressed in terms of the stationary distribution of some embedded process. To find the latter from the (known) transition kernel, we propose a numerical procedure based on discretization and truncation. For some examples we show the method works well, although its performance is clearly affected by the quality of these approximations, both in terms of accuracy and runtime.

This paper deals with an M / G / 1 queue with vacations and multiple phases of operation. If there are no customers in the system at the instant of a service completion, a vacation commences, that is, the system moves to vacation phase 0. If none is found waiting at the end of a vacation, the server goes for another vacation. Otherwise, the system jumps from phase 0 to some operative phase i with probability $$q_i$$ , $$i = 1,2, \ldots ,n.$$ In operative phase i, $$i = 1,2, \ldots ,n$$ , the server serves customers according to the discipline of FCFS (First-come, first-served). Using the method of supplementary variables, we obtain the stationary system size distribution at arbitrary epoch. The stationary sojourn time distribution of an arbitrary customer is also derived. In addition, the stochastic decomposition property is investigated. Finally, we present some numerical results.

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.

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.

We consider a $d$-node tandem queue with arrival process and light-tailed service processes at all queues i.i.d. and independent of each other. We consider three variations of the probability that the number of customers in the system reaches some high level $N$, namely during a busy cycle, in steady state, and upon arrival of a new customer. We show that their decay rates for large $N$ have the same value and give an expression for this value.

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 consider a discrete-time Geo/G/1 queue controlled by the combination of the N and D policies (called ND-policy). In this system, when there are N waiting customers or the service time backlog of all waiting customers exceeds a given threshold D, whichever emerges first, the idle server immediately resumes its service. Under this policy, since the service times of the customers arriving during the idle period, conditioned on the number of these customers, are dependent, and stochastically different from the service times of the customers arriving during the busy period, the customers in the system are classified into two types. Based on this classification, we first derive the probability generating functions and means of the queue length, idle and busy periods, service time backlog, waiting time and sojourn time, where the busy period is first studied in the discrete-time queues involving the D-policy. Next, by analyzing some results and flaws in the work of Gu et al. (J Syst Sci Complex, 2016. doi: 10.1007/s11424-016-4180-y ), we theoretically show the discrepancies that could arise if the conditional dependency of the service times of the customers arriving during the idle period is ignored. Finally, the numerical examples are provided to study the effects of different parameters on the mean queue length. Through an energy consumption optimization problem in wireless sensor networks, the application of our queueing model in the real world is illustrated, and the flaws that resulted from the results by Gu et al. (J Syst Sci Complex, 2016. doi: 10.1007/s11424-016-4180-y ) are numerically revealed.

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 population processor-sharing (PS) queue, with Markovian arrivals and an exponential server. Such a queue can model an interactive computer system consisting of a bank of terminals in series with a central processing unit (CPU). For systems with a large population $N$ and a commensurately rapid service rate, or infrequent arrivals, we obtain various asymptotic results. We analyze the conditional sojourn time distribution of a tagged customer, conditioned on the number $n$ of others in the system at the tagged customer's arrival instant, and also the unconditional distribution. The asymptotics are obtained by a combination of singular perturbation methods and spectral methods. We consider several space/time scales and parameter ranges, which lead to different asymptotic behaviors. We also identify precisely when the finite population model can be approximated by the standard infinite population $M/M/1$-PS queue., 60 pages and 3 figures

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 paper studies a control problem for the multiclass G/G/1 queue for a risk-sensitive cost of the form $$n^{-1}\log E\exp \sum _ic_iX^n_i(T)$$n-1logEexpźiciXin(T), where $$c_i>0$$ci>0 and $$T>0$$T>0 are constants, $$X^n_i$$Xin denotes the class-i queue length process, and the numbers of arrivals and service completions per unit time are of order n. The main result is the asymptotic optimality, as $$n\rightarrow \infty $$nźź, of a priority policy, provided that $$c_i$$ci are sufficiently large. Such a result has been known only in the Markovian (M/M/1) case. The index which determines the priority is explicitly computed in the case of Gamma-distributed interarrival and service times.

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.

Probabilistic yielding behavior is often observed at unsignalized crosswalks, but its impacts on the traffic flow in terms of traffic capacity and associated vehicular delay have not been examined before. The uniqueness of this problem is that neither traffic nor pedestrian flow holds the absolute priority as normally assumed in existing literature. Based on queuing theory, this paper developed traffic capacity and delay formulas considering the probabilistic priority. The proposed capacity equation reduces to the classic formula when the yielding rate equals one. The service time distributions for both queuers and non-queuers were derived, and M/G2/1 queuing model was applied to determine queue length and vehicular delay. Stochastic simulations showed that the proposed capacity and delay formulas precisely match the simulation results. For ease of practical applications, simpler queuing formulas including M/G/1, M/M/1 and M/D/1 were also examined. Noting that the differences between M/G2/1 and M/G/1 mode...

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 considers computational procedures for the waiting time and queue length distributions in stationary multi-class first-come, first-served single-server queues with deterministic impatience times. There are several classes of customers, which are distinguished by deterministic impatience times (i.e., maximum allowable waiting times). We assume that customers in each class arrive according to an independent Poisson process and a single server serves customers on a first-come, first-served basis. Service times of customers in each class are independent and identically distributed according to a phase-type distribution that may differ for different classes. We first consider the stationary distribution of the virtual waiting time and then derive numerically feasible formulas for the actual waiting time distribution and loss probability. We also analyze the joint queue length distribution and provide an algorithmic procedure for computing the probability mass function of the stationary joi...

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...

Bayes estimator of different queueing performance measures are derived in steady state by recording system size from each of n iid M/M/1 queues. The Bayes estimators are obtained under both squared error loss function and precautionary loss function with a bivariate distribution beta stacy as prior, with natural restriction 0 < λ < µ where λ and µ are arrival rate and service rate respectively. A comprehensive simulation results are also shown at the last section.

A research technique is proposed to analyze M/G/1/m queueing systems with hysteretic strategies of random dropping of customers and control of service time. Formulas are obtained to find the Laplace transforms of the distribution of the number of customers in the system during busy period and the distribution function of busy period and to calculate the stationary characteristics. The relations for stationary characteristics are tested on examples by simulation models constructed with the use of GPSS World workbenches.

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.

This note discusses the inter-loss time ofan M/G/1/1 queuing system. The inter-loss time is defined as the time duration between two consecutive losses of arriving customers. In this study, we present the explicit Laplace transform of the inter-loss time distribution of an M/G/1/1 queuing system.

In classical vacation queue models, the server completely stops serving customers during a vacation period. We deal with a system in which the server performs other supplementary jobs at a different rate rather than entirely stopping during this period. The multiple working vacation policy is considered in this study. The stationary probability distribution is obtained by using the matrix geometric method. The number of customers in the system is presented by the stochastic decomposition structure in vacation queue model. Finally, a sensitivity analysis of the model parameters on the performance measures is examined by a numerical study.

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.

We consider an infinite-buffer single-server queue with renewal input and Markovian service process where customers are served in batches according to a general bulk service rule. Queue-length distributions at epochs of pre-arrival, arbitrary and post-departure have been obtained along with some important performance measures such as mean queue lengths and mean waiting times in both the system as well as the queue. We also obtain the steady-state service batch size distributions as well as system-length distributions. The proposed analysis is based on roots of the associated characteristic equation of the vector-generating function of queue-length distribution at a pre-arrival epoch. Also, we provide analytical and numerical comparison between the roots method used in this paper and the matrix geometric method in terms of computational complexities and required computation time to evaluate pre-arrival epoch probabilities for both the methods. Later, we have established heavy- and light-traffic approximations as well as an approximation for the tail probabilities at pre-arrival epoch based on one root of the characteristic equation. Numerical results for some cases have been presented to show the effect of model parameters on the performance measures.