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.     

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

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.     

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.     

Unreliable multi-server system with controllable broadcasting service

Consideration was given to the multi-server queuing system with an infinite buffer. The customer arrivals obey a Markov arrival flow, the time of customer service having a phasetype distribution. service may be done with errors. If at the instant of customer arrival the number of busy servers is less than some threshold, then the customer is copied to all free servers which service it. If at that instant the number of busy servers is not less than some threshold, then the customer is serviced by a single server. The stationary distribution of the number of customers and their sojourn time were determined. The impact of the threshold value on the probability of successful service of the customer was studied numerically.     

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.     

Multi-server queueing system with a Batch Markovian Arrival Process and negative customers

A multi-server queueing system with a finite buffer, where a Batch Markovian Arrival Process (BMAP) arrives, is studied. The servicing time of a customer has a phase-type (PH) distribution. Customers are admitted to the system in accordance with the disciplines of partial admission, complete admission and complete rejection. Except standard (positive) customers, a MAP flow of negative customers arrives to the system. In a random way, a negative customer removes from the system one of the positive customers that are at the server. A stationary distribution of system state probabilities, the Laplace-Stieltjes transformation of the stationary distribution of waiting time, major characteristics of system performance are found. Numerical examples are given.     

Call center operation model as a <Emphasis Type="Italic">MAP/PH/N/R−N</Emphasis> system with impatient customers

We analyze a multiserver queueing system with a finite buffer and impatient customers. The arrival customer flow is assumed to be Markovian. Service times of each server are phase-type distributed. If all servers are busy and a new arrival occurs, it enters the buffer with a probability depending on the total number of customers in the system and waits for service, or leaves the system with the complementary probability. A waiting customer may become impatient and abandon the system. We give an algorithm for finding the stationary distribution of system states and derive formulas for basic performance characteristics. We find Laplace-Stieltjes transforms for sojourn and waiting times. Numeric examples are given.     

A discrete-time retrial queue with negative customers and unreliable server

This paper treats a discrete-time single-server retrial queue with geometrical arrivals of both positive and negative customers in which the server is subject to breakdowns and repairs. Positive customers who find sever busy or down are obliged to leave the service area and join the retrial orbit. They request service again after some random time. If the server is found idle or busy, the arrival of a negative customer will break the server down and simultaneously kill the positive customer under service if any. But the negative customer has no effect on the system if the server is down. The failed server is sent to repair immediately and after repair it is assumed as good as new. We analyze the Markov chain underlying the queueing system and obtain its ergodicity condition. The generating functions of the number of customers in the orbit and in the system are also obtained along with the marginal distributions of the orbit size when the server is idle, busy or down. Finally, some numerical examples show the influence of the parameters on some crucial performance characteristics of the system.     

A multiserver MAP/PH/<Emphasis Type="Italic">N</Emphasis> system with controlled broadcasting by unreliable servers

A multiserver queuing system with an unlimited buffer is considered. The customer arrival is described by the Markov arrival process. The service time has a phase-type distribution. The service may occur with errors. The service strategy is as follows. If the number of busy servers is higher than a certain threshold value at the moment of the customer arrival, then the customer is copied, and the copies are serviced by all the free servers. If the number of busy servers is not higher than this threshold at the moment of the customer arrival, then the customer is serviced by one server. Stationary distributions of the number of customers and the residence time within the system are obtained. The threshold’s influence on the main parameters of the system’s productivity is numerically investigated.     

A Queueing System with Inverse Discipline, Two Types of Customers, and Markov Input Flow

The stationary probabilities of the states of a single-server queueing system with a modified Markov input flow and inverse service with interruption are determined. The service of an interrupted customer, depending on his type, is either resumed or started anew.     

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.     

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.     

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

Queuing systems with Markov arrival process, several customer types, generalized foreground-background processor-sharing discipline with minimal served length or separate finite buffers for customers of different types, or a common finite buffer for customers of all types are studied. Mathematical relations are derived and used to compute the joint stationary distribution of the number of customers of all types in a system.     

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.     

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.     

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

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

Optimal control of parallel queues with impatient customers

We consider a queueing system with a number of identical exponential servers. Each server has its own queue with unlimited capacity. The service discipline in each queue is first-come-first-served (FCFS). Customers arrive according to a state-dependent Poisson process with an arrival rate which is a non-increasing function of the number of customers in the system. Upon arrival, a customer must join a server’s queue according to a stationary state-dependent policy, where the state is taken to be the number of customers in servers’ queues. No jockeying among queues is allowed. Each arriving customer is limited to a generally distributed patience time after which it must depart the system and is considered lost. Two models of customer behavior are considered: deadlines until the beginning of service and deadlines until the end of service. We seek an optimal policy to assign an arriving customer to a server’s queue. We show that, when the distribution of customer impatience satisfies certain property, the policy of joining shortest queue (SQ) stochastically minimizes the number of lost customers during any finite interval in the long run. This property is shown to always hold for the case of deterministic customer impatience.     

An SM2/MSP/n/r System with Random-Service Discipline and a Common Buffer

A multi-server queueing system with a semi-Markov input flow of two types of customers, Markov service, a common buffer of finite capacity, and random-service discipline is investigated. The method of Markov imbedded chain is applied to find the stationary distribution of the main service characteristics of this system. By way of example, a system with phase-type service time distribution is given.