Search

The operation of many queueing systems is adequately described by the structured multidimensional continuous-time Markov chains. The most well-studied classes of such chains are level-independent Quasi-Birth-and-Death processes, GI/M/1 type and M/G/1 type Markov chains, generators of which have the block tri-diagonal, lower- and upper-Hessenberg structure, respectively. All these classes assume that the matrices of transition rates are quasi-Toeplitz. This property greatly simplifies their analysis but makes them inappropriate for the study of many important systems, e.g., retrial queues with a retrial rate depending on the number of customers in orbit, queues with impatient customers, etc. The importance of such systems attracts significant interest to their analysis. However, in the literature, there is a methodological gap relating to the ergodicity condition of the corresponding Markov chains. To fulfill this gap and facilitate the analysis of a wide range of such systems, we show that under non-restrictive assumptions, the following hold true: (i) if the customers can balk or are impatient or non-persistent, then the Markov chain describing the behavior of the system belongs to the class of asymptotically quasi-Toeplitz Markov chains; (ii) this chain is ergodic; (iii) known algorithms can be applied for the calculation of the stationary distribution of the corresponding queueing system.

We consider a multi-server queueing system with a visible queue and an arrival flow that is dynamically dependent on the system’s rating. This rating reflects the level of customer satisfaction with the quality and price of the provided service. A higher rating implies a higher arrival rate, which motivates the service provider to increase the price of the service. A steady-state analysis of this system using the proposed mechanism for changing the rating and a threshold strategy for changing the price is performed. This is carried out via the consideration of a suitably constructed multidimensional Markov chain. The impact of the variation in the threshold defining the strategy for changing the price on the key performance indicators is numerically illustrated. The results can be used to make managerial decisions, leading to an increase in the effectiveness of system operations.

In this paper, we analyze a multi-server queueing system with a marked Markov arrival process of two types of customers and a phase-type distribution of service time depending on the type of customer. Customers of both types are assumed to be impatient and renege from the buffers after an exponentially distributed number of times. The strategy of flexible provisioning of priorities is analyzed. It assumes a randomized choice of the customers from the buffers, with probabilities dependent on the relation between the number of customers in a priority finite buffer and the fixed threshold value. To simplify the construction of the underlying Markov chain and the derivation of the explicit form of its generator, we use the so-called generalized phase-type distribution. It is shown that the created Markov chain fits the category of asymptotically quasi-Toeplitz Markov chains. Using this fact, we show that the considered Markov chain is ergodic for any value of the system parameters and compute its stationary distribution. Expressions for key performance measures are presented. Numerical results that show how the parameters of the control strategy affect the system’s performance measurements are given. It is shown that the results can be used for managerial purposes and that it is crucial to take correlation in the arrival process into account.

A queuing system having two different servers is under study. Demands enter the system according to a Markov arrival process. Service times have phase-type distribution. Service of demands is possible only if the fixed number of energy units, probably different for two servers, is available in the system at the potential service beginning moment. Energy units arrive in the system also according to a Markov arrival process and are stored in a stock (battery) of a finite capacity. Leakage of energy units from the stock can occur. Demands waiting in the infinite buffer are impatient and can leave the buffer after an exponentially distributed waiting time. One server is the main one and permanently provides service when the buffer is not empty and the required number of energy units is available. The second server is the assistant server and is switched on or off depending on the availability of energy units and queue length according to the hysteresis strategy defined by two thresholds. The assistant server is switched on when the queue length is not less than the greater threshold and is switched off when the queue length becomes smaller than the smaller threshold. The use of the assistant server has to be paid. Thus, the problem of the optimal selection of the thresholds defining the control strategy naturally arises. To solve this problem, the study of the behavior of the system under any fixed values of the parameters of the control strategy is necessary. Such a study is given in this paper. Numerical results are presented. They illustrate the feasibility of computer realization of the developed algorithms for computation of the stationary distribution of the system states and the main key performance indicators as well as the result of solving one of the possible optimization tasks.

In this paper, we consider a multi-server queue with a finite buffer. Request arrivals are defined by the Markov arrival process. Service is provided to groups of requests. The minimal and maximal group sizes are fixed. The service time of a group has a phase-type distribution with an irreducible representation depending on the size of the group. The requests are impatient. The patience time for an arbitrary request has an exponential distribution. After this time expires, the request is lost if all servers are busy or, if some server is idle, with a certain probability, all requests staying in the buffer start their service even if their number is below the required minimum. The behavior of the system is described by a multi-dimensional continuous-time Markov chain that does not belong to the class of level-independent quasi-birth-and-death processes. The algorithm for the computation of the stationary distribution of this chain is presented, and expressions for the computation of the queuing system’s performance characteristics are derived. The description of a delivery system operation in terms of the analyzed queuing model is given, and the problem of the optimization of its operation is numerically solved. Multi-server queues with a phase-type distribution for the group service time that are dependent on the size of the group, the account of request impatience, and the correlated arrival process have not previously been analyzed in the existing literature. However, they represent a precise model of many real-world objects, including delivery systems.

In this paper, we consider a single server queueing system in which the arrivals occur according to a Markovian arrival process (MAP). The served customers may be recruited (or opted from those customers’ point of view) to act as secondary servers to provide services to the waiting customers. Such customers who are recruited to be servers are referred to as secondary servers. The service times of the main as well as that of the secondary servers are assumed to be exponentially distributed possibly with different parameters. Assuming that at most there can only be one secondary server at any given time and that the secondary server will leave after serving its assigned group of customers, the model is studied as a QBD-type queue. However, one can also study this model as a GI/M/1-type queue. The model is analyzed in steady state, and a few illustrative numerical examples are presented.

In this paper, we consider a queueing system consisting of two multi-server subsystems that is designed for the service of clients arriving at a system according to a Markovian arrival process (MAP). Arriving clients receive information about the number of clients present in both subsystems and use this information to make a randomized decision to balk (depart without receiving service) or join the system. In the latter case, they also decide which subsystem they would like to join. One subsystem has an infinite buffer, while the buffer of the second subsystem is finite. The service time distribution is exponential in the first subsystem and phase-type in the second subsystem. During the waiting in the chosen buffers, after the random time intervals, each waiting client checks the status of the alternative subsystem. If some server in that subsystem is idle during this epoch, the client immediately leaves the buffer where it has been staying and starts a service in the alternative subsystem. The problem of computing the steady-state distribution of this system is solved. The feasibility of the proposed solution and certain features of the system’s behavior are numerically illustrated.

A multi-server queueing system with two types of requests and preemptive priority of one type is considered as a model of a cell of a cognitive radio system under practical suggestions about the arrival flows. A hysteresis type strategy for server reservation is suggested to mitigate the effect of interruption of service of low priority requests. Under the arbitrarily fixed values of the sets of the thresholds defining this strategy, the behavior of the system is described by a level-dependent multi-dimensional Markov chain. Formulas for computation of values of performance characteristics of the system are derived. Numerical examples illustrating the dependence of the main performance characteristics on the thresholds defining the strategy of control and the numerical solution of the problem of the optimal choice of the thresholds are reported.

In this paper, a multi-server queueing system providing service to two correlated flows of requests was considered. Non-preemptive priority was granted to one flow via the preliminary delay of requests in the intermediate buffers with different rates of extracting from the buffers. Customers’ impatience during waiting in the intermediate and main buffers was taken into account. The possibility of the use of the results of the mathematical analysis for managerial goals is numerically illustrated.

A multi-server infinite buffer queueing system with additional servers (assistants) providing help to the main servers when they encounter problems is considered as the model of real-world systems with customers’ self-service. Such systems are widely used in many areas of human activity. An arrival flow is assumed to be the novel essential generalization of the known Markov Arrival Process (MAP) to the case of the dynamic dependence of the parameters of the MAP on the rating of the system. The rating is the process defined at any moment by the quality of service of previously arrived customers. The possibilities of a customers immediate departure from the system at the entrance to the system and the buffer due to impatience are taken into account. The system is analyzed via the use of the results for multi-dimensional Markov chains with level-dependent behavior. The transparent stability condition is derived, as well as the expressions for the key performance indicators of the system in terms of the stationary probabilities of the Markov chain. Numerical results are provided.

An infinite-server queueing model with state-dependent arrival process and exponential distribution of service time is analyzed. It is assumed that the difference between the value of the arrival rate and total service rate becomes positive starting from a certain value of the number of customers in the system. In this paper, time until reaching this value by the number of customers in the system is called the pseudo steady-state period (PSSP). Distribution of duration of PSSP, its raw moments and its simple approximation under a certain scaling of the number of customers in the system are analyzed. Novelty of the considered problem consists of an arbitrary dependence of the rate of customer arrival on the current number of customers in the system and analysis of time until reaching from below a certain level by the number of customers in the system. The relevant existing papers focus on the analysis of time interval since exceeding a certain level until the number of customers goes down to this level (congestion period). Our main contribution consists of the derivation of a simple approximation of the considered time distribution by the exponential distribution. Numerical examples are presented, which confirm good quality of the proposed approximation.

A novel multi-server vacation queuing model is considered. The distinguishing feature of the model, compared to the standard queues, is the self-sufficiency of servers. A server can terminate service and go on vacation independently of the system manager and the overall situation in the system. The system manager can make decisions whether to allow the server to start work after vacation completion and when to try returning some server from a vacation to process customers. The arrival flow is defined by a general batch Markov arrival process. The problem of optimal choice of the total number of servers and the thresholds defining decisions of the manager arises. To solve this problem, the behavior of the system is described by the three-dimensional Markov chain with the special block structure of the generator. Conditions for the ergodicity of this chain are derived, the problem of computation of the steady-state distribution of the chain is discussed. Expressions for the key performance indicators of the system in terms of the distribution of the chain states are derived. An illustrative numerical result is presented.

We consider a MAP/PH/1-type queueing system with server vacations as a model that is useful for the analysis of multiple access systems with polling discipline without transmission interruption. Vacation of the server corresponds to the service providing competitive information flows to the polling system. In this paper, we consider a vacation queueing model under pretty general assumptions about the probabilistic distributions describing the behavior of the system and the realistic assumption, in many real-world systems, that ongoing service cannot be terminated ahead of schedule. We derive the criterion of the stable operation of the system and the stationary distributions of the system states and the waiting time. An illustrative numerical example is presented.

In this paper, we study a multi-server queueing system with retrials and an infinite orbit. The arrival of primary customers is described by a batch Markovian arrival process (BMAP), and the service times have a phase-type (PH) distribution. Previously, in the literature, such a system was mainly considered under the strict assumption that the intervals between the repeated attempts from the orbit have an exponential distribution. Only a few publications dealt with retrial queueing systems with non-exponential inter-retrial times. These publications assumed either the rate of retrials is constant regardless of the number of customers in the orbit or this rate is constant when the number of orbital customers exceeds a certain threshold. Such assumptions essentially simplify the mathematical analysis of the system, but do not reflect the nature of the majority of real-life retrial processes. The main feature of the model under study is that we considered the classical retrial strategy under which the retrial rate is proportional to the number of orbital customers. However, in this case, the assumption of the non-exponential distribution of inter-retrial times leads to insurmountable computational difficulties. To overcome these difficulties, we supposed that inter-retrial times have a phase-type distribution if the number of customers in the orbit is less than or equal to some non-negative integer (threshold) and have an exponential distribution in the contrary case. By appropriately choosing the threshold, one can obtain a sufficiently accurate approximation of the system with a PH distribution of the inter-retrial times. Thus, the model under study takes into account the realistic nature of the retrial process and, at the same time, does not resort to restrictions such as a constant retrial rate or to rough truncation methods often applied to the analysis of retrial queueing systems with an infinite orbit. We describe the behavior of the system by a multi-dimensional Markov chain, derive the stability condition, and calculate the steady-state distribution and the main performance indicators of the system. We made sure numerically that there was a reasonable value of the threshold under which our model can be served as a good approximation of the BMAP/PH/N queueing system with the PH distribution of inter-retrial times. We also numerically compared the system under consideration with the corresponding queueing system having exponentially distributed inter-retrial times and saw that the latter is a poor approximation of the system with the PH distribution of inter-retrial times. We present a number of illustrative numerical examples to analyze the behavior of the system performance indicators depending on the system parameters, the variance of inter-retrial times, and the correlation in the input flow.

A single-server non-pre-emptive priority queueing system of a finite capacity with many types of customers is analyzed. Inter-arrival times can be correlated and batch arrivals are allowed. Possible unreliability of the server, implying the loss of a customer or the necessity of its service from the early beginning or some phase of the service, is taken into account. Initial priorities provided to various types of customers at the arrival moment can be varied (increased or decreased) after the random amount of time during the customer stay in the buffer. Such a type of queues arises in the modeling operation of various emergency care systems, information, and perishable goods delivering systems, etc. The stationary behavior of the system is described by the finite state multi-dimensional continuous-time Markov chain with the upper-Hessenberg block structure of the generator. The stationary distribution of the system states and some important characteristics of the system are calculated. The presented numerical examples illustrate opportunities to quantitatively evaluate the impact of the buffer capacity and customers’ mean arrival rate on the most important characteristics of the system. The possibility of solving optimization problems is briefly shown.

A new flexible discipline for providing priority to one of two types of customers in a single-server queue is proposed. This discipline assumes the use of additional finite storages for each type of arriving customer. During the stay in a storage, a customer can leave the system or transfer to the main infinite buffer. Preference to priority customers is provided via the proper choice of the rates of a customer transfer from the storages to the buffer. Analysis of this discipline is implemented under quite general assumptions about the arrival and service processes. The advantage of the proposed discipline over the classical non-preemptive discipline is numerically demonstrated.

We consider a queuing network with single-server nodes and heterogeneous customers. The number of customers, which can obtain service simultaneously, is restricted. Customers that cannot be admitted to the network upon arrival make repeated attempts to obtain service. The service time at the nodes is exponentially distributed. After service completion at a node, the serviced customer can transit to another node or leave the network forever. The main features of the model are the mutual dependence of processes of customer arrivals and retrials and the impatience and non-persistence of customers. Dynamics of the network are described by a multidimensional Markov chain with infinite state space, state inhomogeneous behavior and special structure of the infinitesimal generator. The explicit form of the generator is derived. An effective algorithm for computing the stationary distribution of this chain is recommended. The expressions for computation of the key performance measures of the network are given. Numerical results illustrating the importance of the account of the mentioned features of the model are presented. The model can be useful for capacity planning, performance evaluation and optimization of various wireless telecommunication networks, transportation and manufacturing systems.

In this paper, we analyze a multi-server queueing system with heterogeneous customers that arrive according to a marked Markovian arrival process. Customers of two types differ in priorities and parameters of phase type distribution of their service time. The queue under consideration can be used to model the processes of information transmission in telecommunication networks in which often the flow of information is the superposition of several types of flows with correlation of inter-arrival times within each flow and cross-correlation. We define the process of information transmission as the multi-dimensional Markov chain, derive the generator of this chain and compute its stationary distribution. Expressions for computation of various performance measures of the system, including the probabilities of loss of customers of different types, are presented. Output flow from the system is characterized. The presented numerical results confirm the high importance of account of correlation in the arrival process. The values of important performance measures for the systems with the correlated arrival process are essentially different from the corresponding values for the systems with the stationary Poisson arrival process. Measurements in many real world systems show poor approximation of real flows by such an arrival process. However, this process is still popular among the telecommunication engineers due to the evident existing gap between the needs of adequately modeling the real life systems and the current state of the theory of algorithmic methods of queueing theory.

A single-server queueing system with a finite buffer, several types of impatient customers, and non-preemptive priorities is analyzed. The initial priority of a customer can increase during its waiting time in the queue. The behavior of the system is described by a multi-dimensional Markov chain. The generator of this chain, having essential dependencies between the components, is derived and formulas for computation of the most important performance indicators of the system are presented. The dependence of some of these indicators on the capacity of the buffer space is illustrated. The profound effect of the phenomenon of correlation of successive inter-arrival times and variance of the service time is numerically demonstrated. Results can be used for the optimization of dispatching various types of customers in information transmission systems, emergency departments and first aid stations, perishable foods supply chains, etc.

The use of priorities allows us to improve the quality of service of inhomogeneous customers in telecommunication networks, inventory and health-care systems. An important modern direction of research is to analyze systems in which priority of a customer can be changed during his/her stay in the system. We considered a single-server queuing system with a finite buffer, where two types of customers arrive according to a batch marked Markov arrival process. Type 1 customers have non-preemptive priority over type 2 customers. Low priority customers are able to receive high priority after the random amount of time. For each non-priority customer accepted into the buffer, a timer, which counts a random time having a phase type distribution, is switched-on. When the timer expires, the customer with some probability leaves the system unserved and with the complimentary probability gains the high priority. Such a type of queues is typical in many health-care systems, contact centers, perishable inventory, etc. We describe the behavior of the system by a multi-dimensional continuous-time Markov chain and calculate a number of the stationary performance measures of the system including the various loss probabilities as well as the distribution function of the waiting time of priority customers. The illustrative numerical examples giving insights into the system behavior are presented.

We consider a queueing network with a finite number of nodes and servers moving between the nodes as a model of car sharing. The arrival process of customers to various nodes is defined by a marked Markovian arrival process. The customer that arrives at a certain node when there is no idle server (car) is lost. Otherwise, he/she is able to start the service. With known probability, which depends on the node and the number of available cars, this customer can balk the service and leave the system. The service time of a customer has an exponential distribution. Location of the server in the network after service completion is random with the known probability distribution. The behaviour of the network is described by a multi-dimensional continuous-time Markov chain. The generator of this chain is derived which allows us to compute the stationary distribution of the network states. The formulas for computing the key performance indicators of the system are given. Numerical results are presented. They characterize the dependence of some performance measures of the network and the nodes on the total number of cars (fleet size of the car sharing system) and correlation in the arrival process.

The operation of many real-world systems, e.g., servers of data centers, is accompanied by the heating of a server. Correspondingly, certain cooling mechanisms are used. If the server becomes overheated, it interrupts processing of customers and needs to be cooled. A customer is lost when its service is interrupted. To prevent overheating and reduce the customer loss probability, we suggest temporal termination of service of new customers when the temperature of the server reaches the predefined threshold value. Service is resumed after the temperature drops below another threshold value. The problem of optimal choice of the thresholds (with respect to the chosen economical criterion) is numerically solved under quite general assumptions about the parameters of the system (Markovian arrival process, phase-type distribution of service time, and accounting for customers impatience). Numerical examples are presented.