Markov queueing system with finite buffer and negative customers affecting the queue end

A multiserver queueing system with finite buffer, Markov input flow, and Markov (general) service process of all customers on servers with the number of process states and intensities of inter-phase transitions depending on the number of customers in the system is considered. A Markov flow of negative customers arrives to the system; one negative customer “kills” one positive customer at the end of the queue. A recurrent algorithm for computing stationary probabilities of system states is obtained; and a method for calculating stationary distribution of waiting time before starting service of a positive customer is proposed.     

Analysis of the multi-server Markov queuing system with unlimited buffer and negative customers

Consideration was given to the multi-server queuing system with unlimited buffer, Markov input flow, and Markov (general) process of servicing all customers on servers with the number of process states and intensities of the inter-phase passage depending on the number of customers in the system. Additionally, a Markov flow of negative customers arrives to the system, the arriving negative customer killing the last queued positive customer. A recurrent algorithm to calculate the stationary probabilities of system states was obtained, and a method of calculation of the stationary distribution of the waiting time before starting servicing of a positive customer was proposed.     

Two-channel MAP/PH/2 system with customer resequencing

Consideration was given to the two-server queuing system with resequencing buffer and customer resequencing to which a Markov customer flow arrives. The resequencing buffer has also an infinite capacity. The time of customer servicing by each server has the same phasetype distribution. A recurrent algorithm was proposed for calculation of the joint stationary distribution of the numbers of customers in the buffer and resequencing buffer. The stationary distributions of the customer sojourn time in the system and resequencing buffer were obtained in terms of the Laplace–Stieltjes transform in the form of infinite sums. Examples of calculations of the established relations were given.     

G-Networks: Development of the Theory of Multiplicative Networks

This is a review on G-networks, which are the generalization of the Jackson and BCMP networks, for which the multi-dimensional stationary distribution of the network state probabilities is also represented in product form. The G-networks primarily differ from the Jackson and BCMP networks in that they additionally contain a flow of the so-called negative customers and/or triggers. Negative customers and triggers are not served. When a negative customer arrives at a network node, one or a batch of positive (ordinary) customers is killed (annihilated, displaced), whereas a trigger displaces a positive customer from the node to some other node. For applied mathematicians, G-networks are of great interest for extending the multiplicative theory of queueing networks and for practical specialists in modeling computing systems and networks and biophysical neural networks for solving pattern recognition and other problems.     

新颖的离散时间队列系统模型(英文)

带有正负顾客的连续时间单台服务器的队列系统得到了深入研究且已应用于多agent服务系统和计算机网络系统,而带有正负顾客的离散时间Geo/Geo/1队列研究在最近才出现。在拓展离散时间单台服务器Geo/Geo/1队列的基础上,提出了一个具有正负几何到达顾客的离散时间单台服务器GI/M/1队列模型,分析了队列静态长度分布和在RCH与RCE情况下的等待时间长度分布。     

Single server retrial queue with group admission of customers

We consider a retrial queueing system with a single server and novel customer׳s admission discipline. The input flow is described by a Markov Arrival Process. If an arriving customer meets the server providing the service, it goes to the orbit and repeats attempts to get service in random time intervals whose duration has exponential distribution with parameter dependent on the customers number in orbit. Server operates as follows. After a service completion epoch, customers admission interval starts. Duration of this interval has phase type distribution. During this interval, primary customers and customers from the orbit are accepted to the pool of customers which will get service after the admission interval. Capacity of this pool is limited and after the moment when the pool becomes full before completion of admission interval all arriving customers move to the orbit. After completion of an admission interval, all customers in the pool are served simultaneously by the server during the time having phase type distribution depending on the customers number in the pool. Using results known for Asymptotically Quasi-Toeplitz Markov Chains, we derive stability condition of the system, compute the stationary distribution of the system states, derive formulas for the main performance measures and numerically show advantages of the considered customer׳s admission discipline (higher throughput, smaller average number of customers in the system, higher probability to get a service without visiting the orbit) in case of proper choice of the capacity of the pool and the admission period duration.     

A discrete-time on–off source queueing system with negative customers

This paper studies a discrete-time single-server infinite-capacity queueing system with correlated arrivals, geometrically distributed service times and negative customers. Positive customers are generated by a Bernoulli bursty source, with geometrically distributed lengths of the on-periods and off-periods. Negative customers arrive to the system according to a geometrical arrival process which is independent of the positive arrival process. A negative customer removes a positive customer in service if any, but has no effect on the system if it finds the system empty. We analyze the Markov chain underlying the queueing system and evaluate the performance of the system based on generating functions technique. Closed-form expressions of some performance measures of the system are obtained, such as stationary probability generating functions of queue length, unfinished work, sojourn time distribution and so on. Finally, the effect of several parameters on the system is shown numerically.     

Virtual Waiting Time in the Single-server Queuing System with Unreliable Server

The unreliable queuing system was considered both in the stationary and nonstationary modes. A Poisson flow of customers arrives to the system. The flow of stable failures makes up the renewal process, and the inter-failure intervals are distributed hyperexponentially. The times of customer servicing and renewal of the servicing system are distributed arbitrarily. The virtual waiting time was established.     

Exponential queuing system with negative customers and bunker for ousted customers

Consideration was given to the queuing system with Poisson flows of incoming positive and negative customers. For the positive customers, there is an infinite-capacity buffer. The arriving negative customer knocks out a positive customer queued in the buffer and moves it to an infinite-capacity buffer of ousted customers (bunker). If the buffer is empty, then the negative customer discharges the system without affecting it. After servicing the current customer, the server receives a customer from the buffer or, if the buffer is empty, the bunker. The customers arriving from both the buffer and bunker are distributed exponentially with the same parameter. Relations for calculation of the stationary distributions of the queues in the buffer and bunker were obtained.     

A Single-Server Queueing System with Background Customers

A single-server queueing system with a Markov flow of primary customers and a flow of background customers from a bunker containing unbounded number of customers, i.e., the background customer flow is saturated, is studied. There is a buffer of finite capacity for primary customers. Service processes of primary as well as background customers are Markovian. Primary customers have a relative service priority over background customers, i.e., a background customer is taken for service only if the buffer is empty upon completion of service of a primary customer. A matrix algorithm for computing the stationary state probabilities of the system at arbitrary instants and at instants of arrival and completion of service of primary customers is obtained. Main stationary performance indexes of the system are derived. The Laplace—Stieltjes transform of the stationary waiting time distribution for primary customers is determined.__________Translated from Avtomatika i Telemekhanika, No. 6, 2005, pp. 74–88.Original Russian Text Copyright © 2005 by Bocharov, Shlumper.     

A MAP K /G K /1/∞ Queueing System with Generalized Foreground-Background Processor Sharing Discipline

A queueing system with Markov arrival process, several customer types, generalized foreground-background processor sharing discipline with minimal served length, and an infinite buffer for all types of customers is studied. The joint stationary distribution of the number of customers of all types and the stationary distribution of time of sojourn of customers of every type are determined in terms of generating functions and Laplace–Stieltjes transforms.     

The stationary distribution invariance of states in a closed queueing network with temporarily non-active customers

A stationary functioning of a closed queueing network with temporarily non-active customers is analyzed. Non-active customers are located at network nodes in queues, being not serviced. For a customer, the feasibility of passing from its ordinary state to the temporarily non-active state (and backwards) is provided. Service times of customers at different nodes possess arbitrary distributions. Finally, the stationary distribution invariance of network states is established with respect to the functional form of customer service time distributions under fixed first-order moments.     

Geom/G/1/n system with LIFO discipline without interrupts and constrained total amount of customers

Consideration was given to the discrete-time queuing system with inversive servicing without interrupts, second-order geometrical arrivals, arbitrary (discrete) distribution of the customer length, and finite buffer. Each arriving customer has length and random volume. The total volume of the customers sojourning in the system is bounded by some value. Formulas of the stationary state probabilities and stationary distribution of the time of customer sojourn in the system were established.     

A multi-server perishable inventory system with negative customer

In this paper, we consider a continuous review perishable inventory system with multi-server service facility. In such systems the demanded item is delivered to the customer only after performing some service, such as assembly of parts or installation, etc. Compared to many inventory models in which the inventory is depleted at the demand rate, however in this model, it is depleted, at the rate at which the service is completed. We assume that the arrivals of customers are according to a Markovian arrival process (MAP) and that the service time has exponential distribution. The ordering policy is based on (s, S) policy. The lead time is assumed to have exponential distribution. The customer who finds either all servers are busy or no item (excluding those in service) is in the stock, enters into an orbit of infinite size. These orbiting customers send requests at random time points for possible selection of their demands for service. The interval time between two successive request-time points is assumed to have exponential distribution. In addition to the regular customers, a second flow of negative customers following an independent MAP is also considered so that a negative customer will remove one of the customers from the orbit. The joint probability distribution of the number of busy servers, the inventory level and the number of customers in the orbit is obtained in the steady state. Various measures of stationary system performance are computed and the total expected cost per unit time is calculated. The results are illustrated numerically.     

Retrial queuing system with Markovian arrival flow and phase-type service time distribution

We consider a multi-server queuing system with retrial customers to model a call center. The flow of customers is described by a Markovian arrival process (MAP). The servers are identical and independent of each other. A customer’s service time has a phase-type distribution (PH). If all servers are busy during the customer arrival epoch, the customer moves to the buffer with a probability that depends on the number of customers in the system, leaves the system forever, or goes into an orbit of infinite size. A customer in the orbit tries his (her) luck in an exponentially distributed arbitrary time. During a waiting period in the buffer, customers can be impatient and may leave the system forever or go into orbit. A special method for reducing the dimension of the system state space is used. The ergodicity condition is derived in an analytically tractable form. The stationary distribution of the system states and the main performance measures are calculated. The problem of optimal design is solved numerically. The numerical results show the importance of considering the MAP arrival process and PH service process in the performance evaluation and capacity planning of call centers.     

Queuing system with processor sharing and limited resources

Consideration was given to a processor-sharing system with heterogeneous customers serviced by system resources of two types: the first, discrete, type necessarily consists of an integer number N of units (servers), and the second type (memory) may be discrete or continuous. The customer type is defined by the number of units of the first-type resources required to service it. In addition to the need for the first-type resource, each customer is characterized by a certain volume, that is, the amount of the second-type resource required to service it. The total amount of customers (total busy resource of the second type) in the system is limited by a certain positive value (memory space) V. The customer volume and its length (amount of work required to service it) are generally dependent. Their joint distribution also depends on the customer type. For this system, the stationary distribution of the number of customers sojourning in the system and the probabilities of losing customers of each type were determined.     

Stationary distribution of the closed queuing network with batch transitions of customers

Consideration was given to the closed queuing network with batch jockeying customers. This network extends the Gordon-Newell model to the case of batch customer servicing. The serviced batch discharges a node without changing its size and arrives to another node with a probability depending on its size. Some constraints must be imposed on the servicing process. The form of the stationary distribution was established, and an efficient algorithm to determine it was proposed.     

Decomposition of Queueing Networks with Dependent Service and Negative Customers

Queueing networks with negative customers (G-networks) and dependent service at different nodes are studied. Every customer arriving at the network is defined by a set of random parameters: his route over the network (a sequence of nodes visited by the customers), route length, and volume and service length of the customer at every stage of the route. For G-networks, which are the analogs of BCMP-networks, the multidimensional stationary distribution of the network state probabilities is shown to be representable in product form.     

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

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

A finite source multi-server inventory system with service facility

In this article, we study a continuous review retrial inventory system with a finite source of customers and identical multiple servers in parallel. The customers arrive according a quasi-random process. The customers demand unit item and the demanded items are delivered after performing some service the duration of which is distributed as exponential. The ordering policy is according to (s, S) policy. The lead times for the orders are assumed to have independent and identical exponential distributions. The arriving customer who finds all servers are busy or all items are in service, joins an orbit. These orbiting customer competes for service by sending out signals at random times until she finds a free server and at least one item is not in the service. The inter-retrial times are exponentially distributed with parameter depending on the number of customers in the orbit. The joint probability distribution of the number of customer in the orbit, the number of busy servers and the inventory level is obtained in the steady state case. The Laplace–Stieltjes transform of the waiting time distribution and the moments of the waiting time distribution are calculated. Various measures of stationary system performance are computed and the total expected cost per unit time is calculated. The results are illustrated numerically.