The M/M/1 queue with inventory, lost sale, and general lead times

We consider an M/M/1 queueing system with inventory under the $(r,Q)$ policy and with lost sales, in which demands occur according to a Poisson process and service times are exponentially distributed. All arriving customers during stockout are lost. We derive the stationary distributions of the joint queue length (number of customers in the system) and on-hand inventory when lead times are random variables and can take various distributions. The derived stationary distributions are used to formulate long-run average performance measures and cost functions in some numerical examples.     

<Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1 type queueing-inventory systems with postponed work,reservation, cancellation and common life time

In this paper we analyze two single server queueing-inventory systems in which items in the inventory have a random common life time. On realization of common life time, all customers in the system are flushed out. Subsequently the inventory reaches its maximum level S through a (positive lead time) replenishment for the next cycle which follows an exponential distribution. Through cancellation of purchases, inventory gets added until their expiry time; where cancellation time follows exponential distribution. Customers arrive according to a Poisson process and service time is exponentially distributed. On arrival if a customer finds the server busy, then he joins a buffer of varying size. If there is no inventory, the arriving customer first try to queue up in a finite waiting room of capacity K. Finding that at full, he joins a pool of infinite capacity with probability γ (0 < γ < 1); else it is lost to the system forever. We discuss two models based on ‘transfer’ of customers from the pool to the waiting room / buffer. In Model 1 when, at a service completion epoch the waiting room size drops to preassigned number L ? 1 (1 < L < K) or below, a customer is transferred from pool to waiting room with probability p (0 < p < 1) and positioned as the last among the waiting customers. If at a departure epoch the waiting room turns out to be empty and there is at least one customer in the pool, then the one ahead of all waiting in the pool gets transferred to the waiting room with probability one. We introduce a totally different transfer mechanism in Model 2: when at a service completion epoch, the server turns idle with at least one item in the inventory, the pooled customer is immediately taken for service. At the time of a cancellation if the server is idle with none, one or more customers in the waiting room, then the head of the pooled customer go to the buffer directly for service. Also we assume that no customer joins the system when there is no item in the inventory. Several system performance measures are obtained. A cost function is discussed for each model and some numerical illustrations are presented. Finally a comparison of the two models are made.     

A multiserver retrial queue: regenerative stability analysis

We consider a multiserver retrial GI/G/m queue with renewal input of primary customers, interarrival time τ with rate , service time S, and exponential retrial times of customers blocked in the orbit. In the model, an arriving primary customer enters the system and gets a service immediately if there is an empty server, otherwise (if all m servers are busy) he joins the orbit and attempts to enter the system after an exponentially distributed time. Exploiting the regenerative structure of the (non-Markovian) stochastic process representing the total number of customers in the system (in service and in orbit), we determine stability conditions of the system and some of its variations. More precisely, we consider a discrete-time process embedded at the input instants and prove that if and , then the regeneration period is aperiodic with a finite mean. Consequently, this queue has a stationary distribution under the same conditions as a standard multiserver queue GI/G/m with infinite buffer. To establish this result, we apply a renewal technique and a characterization of the limiting behavior of the forward renewal time in the (renewal) process of regenerations. The key step in the proof is to show that the service discipline is asymptotically work-conserving as the orbit size increases. Included are extensions of this stability analysis to continuous-time processes, a retrial system with impatient customers, a system with a general retrial rate, and a system with finite buffer for waiting primary customers. We also consider the regenerative structure of a multi-dimensional Markov process describing the system. This work is supported by Russian Foundation for Basic Research under grants 04-07-90115 and 07-07-00088.     

Stability analysis of GI/GI/c/K retrial queue with constant retrial rate

We consider a finite buffer capacity GI/GI/c/K-type retrial queueing system with constant retrial rate. The system consists of a primary queue and an orbit queue. The primary queue has \(c\) identical servers and can accommodate up to \(K\) jobs (including \(c\) jobs under service). If a newly arriving job finds the primary queue to be full, it joins the orbit queue. The original primary jobs arrive to the system according to a renewal process. The jobs have i.i.d. service times. The head of line job in the orbit queue retries to enter the primary queue after an exponentially distributed time independent of the length of the orbit queue. Telephone exchange systems, medium access protocols, optical networks with near-zero buffering and TCP short-file transfers are some telecommunication applications of the proposed queueing system. The model is also applicable in logistics. We establish sufficient stability conditions for this system. In addition to the known cases, the proposed model covers a number of new particular cases with the closed-form stability conditions. The stability conditions that we obtained have clear probabilistic interpretation.     

A single server queue with gated processor-sharing discipline

In this paper we consider a single server queue in which arrivals occur according to a Poisson process and each customer's service time is exponentially distributed. The server works according to the gated process-sharing discipline. In this discipline, the server provides service to a batch of at mostm customers at a time. Once a batch of customers begins service, no other waiting customer can receive service until all members of the batch have completed their service. For this queue, we derive performance characteristics, such as waiting time distribution, queue length distribution etc. For this queue, it is possible to obtain the mean conditional response time for a customer whose service time is known. This conditional response time is a nonlinear function (as opposed to the linear case for the ordinary processor-sharing queue). A special case of the queue (wherem=) has an interesting and unusual solution. For this special case, the size of the batch for service is a Markov chain whose steady state distribution can be explicitly written down. Apart from the contribution to the theory of Markov chains and queues, the model may be applicable to scheduling of computer and communication systems.     

Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers

The model is a service system, consisting of several large server pools. A server’s processing speed and buffer size (which may be finite or infinite) depend on the pool. The input flow of customers is split equally among a fixed number of routers, which must assign customers to the servers immediately upon arrival. We consider an asymptotic regime in which the total customer arrival rate and pool sizes scale to infinity simultaneously, in proportion to a scaling parameter n, while the number of routers remains fixed. We define and study a multi-router generalization of the pull-based customer assignment (routing) algorithm PULL, introduced in Stolyar (Queueing Syst 80(4): 341–361, 2015) for the single-router model. Under the PULL algorithm, when a server becomes idle it sends a “pull-message” to a randomly uniformly selected router; each router operates independently—it assigns an arriving customer to a server according to a randomly uniformly chosen available (at this router) pull-message, if there is any, or to a randomly uniformly selected server in the entire system otherwise. Under Markov assumptions (Poisson arrival process and independent exponentially distributed service requirements), and under subcritical system load, we prove asymptotic optimality of PULL: as \(n\rightarrow \infty \), the steady-state probability of an arriving customer experiencing blocking or waiting vanishes. Furthermore, PULL has an extremely low router–server message exchange rate of one message per customer. These results generalize some of the single-router results in Stolyar (2015).     

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

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

A large closed queueing network with autonomous service and bottleneck

This paper studies the queue-length process in a closed Jackson-type queueing network with the large number N of homogeneous customers by methods of the theory of martingales and by the up- and down-crossing method. The network considered here consists of a central node (hub), being an infinite-server queueing system with exponentially distributed service times, and k single-server satellite stations (nodes) with generally distributed service times with rates depending on the value N. The service mechanism of these k satellite stations is autonomous, i.e., every satellite server j serves the customers only at random instants that form a strictly stationary and ergodic sequence of random variables. Assuming that the first k-1 satellite stations operate in light usage regime the paper considers the cases where the kth satellite station is a bottleneck node. The approach of the paper is based both on development of the method from the paper by Kogan and Liptser [16], where a Markovian version of this model has been studied, and on development of the up- and down-crossing method. This revised version was published online in June 2006 with corrections to the Cover Date.     

Multi-server queueing systems with cooperation of the servers

In this paper, we consider an N-server queueing model with homogeneous servers in which customers arrive according to a stationary Poisson arrival process. The service times are exponentially distributed. Two new customer’s service disciplines assuming simultaneous service of arriving customer by all currently idle servers are discussed. The steady state analysis of the queue length and sojourn time distribution is performed by means of the matrix analytic methods. Numerical examples, which illustrate advantage of introduced disciplines comparing to the classical one, are presented.     

Stochastic comparisons for bulk queues

We consider two important classes of single-server bulk queueing models: M^(X)/G^(Y)/1 with Poisson arrivals of customer groups, and G^(X)/m^(Y)1 with batch service times having exponential density. In each class we compare two systems and prove that one is more congested than the other if their basic random variables are stochastically ordered in an appropriate manner. However, it must be recognized that a system that appears congested to customers might be working efficiently from the system manager's point of view. We apply the results of this comparison to (i) the family {M/G^(s)/1,s 1} of systems with Poisson input of customers and batch service times with varying service capacity; (ii) the family {G^(s)/1,s 1} of systems with exponential customer service time density and group arrivals with varying group size; and (iii) the family {M/D/s,s 1} of systems with Poisson arrivals, constant service time and varying number of servers. Within each family, we find the system that is the best for customers, but this turns out to be the worst for the manager (or vice versa). We also establish upper (or lower) bounds for the expected queue length in steady state and the expected number of batches (or groups) served during a busy period. The approach of the paper is based on the stochastic comparison of random walks underlying the models.This research was partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.     

The Equilibrium Behavior of Reversible Coagulation-Fragmentation Processes

The coagulation-fragmentation process models the stochastic evolution of a population of N particles distributed into groups of different sizes that coagulate and fragment at given rates. The process arises in a variety of contexts and has been intensively studied for a long time. As a result, different approximations to the model were suggested. Our paper deals with the exact model which is viewed as a time-homogeneous interacting particle system on the state space _N, the set of all partitions of N. We obtain the stationary distribution (invariant measure) on _N for the whole class of reversible coagulation-fragmentation processes, and derive explicit expressions for important functionals of this measure, in particular, the expected numbers of groups of all sizes at the steady state. We also establish a characterization of the transition rates that guarantee the reversibility of the process. Finally, we make a comparative study of our exact solution and the approximation given by the steady-state solution of the coagulation-fragmentation integral equation, which is known in the literature. We show that in some cases the latter approximation can considerably deviate from the exact solution.     

Sojourn times in a processor sharing queue with service interruptions

We study the sojourn times of customers in an M/M/1 queue with the processor sharing service discipline and a server that is subject to breakdowns. The lengths of the breakdowns have a general distribution, whereas the on-periods are exponentially distributed. A branching process approach leads to a decomposition of the sojourn time, in which the components are independent of each other and can be investigated separately. We derive the Laplace–Stieltjes transform of the sojourn-time distribution in steady state, and show that the expected sojourn time is not proportional to the service requirement. In the heavy-traffic limit, the sojourn time conditioned on the service requirement and scaled by the traffic load is shown to be exponentially distributed. The results can be used for the performance analysis of elastic traffic in communication networks, in particular, the ABR service class in ATM networks, and best-effort services in IP networks.     

Numerical investigation of a multiserver retrial model

We consider a queueing model in which customers arrive in a Poisson stream to be served by one ofc servers. Each arriving customer enters a pool of active customers and starts generating requests for service at exponentially distributed time intervals at rate until he finds a free server and begins service. An analytical solution of this model is difficult and does not lend itself to numerical implementation. In this paper, we make a simplifying approximation, based on understanding of the physical behavior of the system, which yields an infinitesimal generator with a modified matrix-geometric equilibrium probability vector. That vector can be very efficiently computed even for high congestion levels. Illustrative numerical examples demonstrate the effectiveness of the approximation as well as the effect of the retrial rate on the system behavior for various levels of congestion. This study shows how numerical results for analytically intractable systems can be obtained by combining intuition with efficient algorithmic methods.This author's research was supported in part by Grants Nos. ECS-88-03061 from the National Science Foundation and AFOSR-88-0076 from the Air Force Office of Scientific Research.     

Workload and busy period for M/GI/1 with a general impatience mechanism

The paper deals with the workload and busy period for the $M/GI/1$ M / G I / 1 system with impatience under FCFS discipline. The customers may become impatient during their waiting for service with generally distributed maximal waiting times and also during their service with generally distributed maximal service times depending on the time waited for service. This general impatience mechanism was originally introduced by Kovalenko (1961) and considered by Daley (1965), too. It covers the special cases of impatience on waiting times as well as impatience on sojourn times, for which Boxma et al. (2010, 2011) gave new results and outlined special cases recently. Our unified approach bases on the vector process of workload and busy time. Explicit representations for the LSTs of workload and busy period are given in case of phase-type distributed impatience.     

Optimal Hysteretic Control for the BMAP/G/ 1 System with Single and Group Service Modes

In this paper, we consider a single server queuing model with an infinite buffer in which customers arrive according to a batch Markovian arrival process (BMAP). The services are offered in two modes. In mode 1, the customers are served one at a time and in mode 2 customers are served in groups of varying sizes. Various costs for holding, service and switching are imposed. For a given hysteretic strategy, we derive an expression for the cost function from which an optimal hysteretic control can be obtained. Illustrative numerical examples are presented.     

On stationary queue length distributions for G/M/s/r queues

Consider aG/M/s/r queue, where the sequence{A _n } _n=– of nonnegative interarrival times is stationary and ergodic, and the service timesS _n are i.i.d. exponentially distributed. (SinceA _n =0 is possible for somen, batch arrivals are included.) In caser < , a uniquely determined stationary process of the number of customers in the system is constructed. This extends corresponding results by Loynes [12] and Brandt [4] forr= (with=ES₀/EA₀<s) and Franken et al. [9], Borovkov [2] forr=0 ors=. Furthermore, we give a proof of the relation min(i, s)¯p(i)=p(i–1), 1ir + s, between the time- and arrival-stationary probabilities¯p(i) andp(i), respectively. This extends earlier results of Franken [7], Franken et al. [9].     

On the M/G/1 retrial queueing system with linear control policy

Summary This paper is concerned with the study of a newM/G/1 retrial queueing system in which the delays between retrials are exponentially distributed random variables with linear intensityg(n)=α+nμ, when there aren≥1 customers in the retrial group. This new retrial discipline will be calledlinear control policy. We carry out an extensive analysis of the model, including existence of stationary regime, stationary distribution of the embedded Markov chain at epochs of service completions, joint distribution of the orbit size and the server state in steady state and busy period. The results agree with known results for special cases.     

Analysis of the BMAP/G/1 retrial system with search of customers from the orbit

We consider a single server retrial queuing model in which customers arrive according to a batch Markovian arrival process. Any arriving batch finding the server busy enters into an orbit. Otherwise one customer from the arriving batch enters into service immediately while the rest join the orbit. The customers from the orbit try to reach the service later and the inter-retrial times are exponentially distributed with intensity depending (generally speaking) on the number of customers on the orbit. Additionally, the search mechanism can be switched-on at the service completion epoch with a known probability (probably depending on the number of customers on the orbit). The duration of the search is random and also probably depending on the number of customers in the orbit. The customer, which is found as the result of the search, enters the service immediately if the server is still idle. Assuming that the service times of the primary and repeated customers are generally distributed (with possibly different distributions), we perform the steady state analysis of the queueing model.