Analysis on queueing systems with synchronous vacations of partial servers

We study an M/M/c queue with server vacations. In this queueing system, d (≤c) of c servers take synchronous vacations when these d servers become idle at a service completion instant. This type of queueing model captures the major characteristics of a stochastic service system which processes both random arriving jobs and constantly available jobs. In this paper, the multi-server vacation queueing system has been analyzed as a quasi-birth and death process. Using matrix geometric method, we obtain the stationary distributions of queue length and waiting time and demonstrate the conditional stochastic decomposition property of the queue length and waiting time in this system.     

基于OPNET的排队模型网络仿真

利用OPNET对排队论中的M/M/S服务系统模型进行仿真,得出数据包到达的平均速率、数据包平均大小、服务台个数、服务台平均服务速率等参数的改变,可以影响数据包平均延时和队列长度平均时间,也可以影响系统的稳定性。     

Control of a Heterogeneous Two-Server Exponential Queueing System

A dynamic control policy known as "threshold queueing" is defined for scheduling customers from a Poisson source on a set of two exponential servers with dissimilar service rates. The slower server is invoked in response to instantaneous system loading as measured by the length of the queue of waiting customers. In a threshold queueing policy, a specific queue length is identified as a "threshold," beyond which the slower server is invoked. The slower server remains busy until it completes service on a customer and the queue length is less than its invocation threshold. Markov chain analysis is employed to analyze the performance of the threshold queueing policy and to develop optimality criteria. It is shown that probabilistic control is sub-optimal to minimize the mean number of customers in the system. An approximation to the optimum policy is analyzed which is computationally simple and suffices for most operational applications.     

Processor sharing: A survey of the mathematical theory

During last few decades the Egalitarian Processor Sharing (EPS) has gained a prominent role in applied probability, especially, in queueing theory and its computer applications. While the EPS paradigm emerged in 1967 as an idealization of round-robin (RR) scheduling algorithm in time-sharing computer systems, it has recently capture renewed interest as a powerful concept for modeling WEB servers. This paper summarizes the most important results concerning the exact solutions for the M/GI/1 queue with egalitarian processor sharing. The material is drawn, mainly, from recent authors’ papers which are supplemented, in small degree, by other related results. Many of the further results are established under the direct influence of our earlier papers. Our main purpose is to give a survey of state-of-the-art with regard to main achievements of the contemporary theory of the M/GI/1 queueing system with processor sharing. The focus is on the methods and techniques of exact and asymptotic analysis of this queueing system. In contrast to the standard surveys, the abridged proofs (or their ideas) of some key theorems and corollaries are included in the paper. We outline recent developments in exact analysis of the M/GI/1-EPS queue with further emphasis on time-dependent (transient) probability distributions of the main characteristics. In particular, the present paper includes the results on the joint time-dependent distribution of the sojourn time of a job arriving at time t with the service demand (length) u, and of the number of jobs at time t- in the M/GI/1 queue with egalitarian processor sharing, which obtained in form of multiple transforms. We also show how the non-stationary solutions can be used to obtain known and new results which allow to predict the behaviour of the EPS queue and to yield additional insights into its new unexpected properties. We also discuss a number of limit theorems arising under the study of the processor sharing queues.     

Optimal control of a queueing system with two heterogeneous servers

The problem considered is that of optimally controlling a queueing system which consists of a common buffer or queue served by two servers. The arrivals to the buffer are Poisson and the servers are both exponential, but with different mean service times. It is shown that the optimal policy which minimizes the mean sojourn time of customers in the system is of threshold type. The faster server should be fed a customer from the buffer whenever it becomes available for service, but the slower server should be utilized if and only if the queue length exceeds a readily computed threshold value.     

Study of a Controllable Queueing System with Unreliable Heterogeneous Servers

We consider a two-channel Markov queueing system with unreliable heterogeneous servers and a common queue. The claims are distributed among the servers with a threshold control policy. According to this policy, a server with the smaller average usage cost must be busy if the system itself is not empty, and the other server is used if the number of customers in the queue exceeds a certain threshold. We analyze the system in stationary mode. We present a method for computing the probabilities of system states and expressions for average performance and reliability characteristics. For the problem of minimizing average losses per unit of time, we obtain a heuristic formula that approximately computes the optimal threshold policy and proposes a method for computing the stationary distribution of the claim waiting time in the system.     

Performance prediction of loss and delay Markovian queueing model with nopassing and removable additional servers

In this investigation, the loss and delay Markovian queueing system with nopassing is proposed. The customers may balk or renege with certain probability, on finding all servers busy on their arrival. To cope up with the balking and reneging behaviour of the customers, there is provision of removable additional servers apart from permanent servers so as to provide the better grade of service at optimal cost operating conditions. The customers are classified into two classes depending upon whether they can wait or lost when all servers are busy. The customers can also be categorized into two classes from service point of view. Type A customers have zero service time whereas type B customers have exponential service time. The explicit expressions for the average number of customers in the system, the expected waiting time for both types of customers, etc., are derived by using steady-state queue size distribution. Some earlier results are deduced by setting appropriate system parameters. The system behaviour is examined with the help of numerical illustrations by varying different parameters.Scope and purposeThe performance prediction of various systems in communication switching network, remote border security check post, jobs processing in computers, etc., are influenced by the customers behaviour, in particular, when nopassing constraints are prevalent. The incorporation of loss and delay phenomena is likely to bring about understanding whether the customers would like to wait in the queue or would be lost in case when all servers are busy. The provision of additional removable servers will be helpful in upgrading the service and to reduce the discouragement behaviour of the customers in such congestion situations.     

A recursive algorithm for generating the transition matrices of multistation multiserver exponential reliable queueing networks

This paper is concerned with reliable multistation series queueing networks. Items arrive at the first station according to a Poisson distribution and an operation is performed on each item by a server at each station. Every station is allowed to have more than one server with the same characteristics. The processing times at each station are exponentially distributed. Buffers of nonidentical finite capacities are allowed between successive stations. The structure of the transition matrices of these specific type of queueing networks is examined and a recursive algorithm is developed for generating them. The transition matrices are block-structured and very sparse. By applying the proposed algorithm the transition matrix of a K-station network can be created for any K. This process allows one to obtain the exact solution of the large sparse linear system by the use of the Gauss–Seidel method. From the solution of the linear system the throughput and other performance measures can be calculated.Scope and purposeThe exact analysis of queueing networks with multiple servers at each workstation and finite capacities of the intermediate queues is extremely difficult as for even the case of exponential operation (service or processing) times the Markovian chain that models the system consists of a huge number of states which grows exponentially with the number of stations, the number of servers at each station and the queue capacity of each intermediate queue of the resulting system. The scope and purpose of the present paper is to analyze and provide a recursive algorithm for generating the transition matrices of multistation multiserver exponential reliable queueing networks. By applying the proposed algorithm one may create the transition matrix of a K-station queueing network for any K. This process allows one to obtain the exact solution of the resulting large sparse linear system by the use of the Gauss–Seidel method. From the solution of the linear system the throughput and other performance measures of the system can be obtained.     

A tandem queue with general bulk service and servers' “vacation”

This paper analyses two queueing models consisting of two units I and II connected in series, separated by a finite buffer of size N. In both models, unit I has only one exponential server capable of serving customers one at a time and unit II consist of c parallel exponential servers, each of them serving customers in groups according to general bulk service rules. When the queue length in front of unit II is less than the minimum of batch size, the free servers take a vacation. On return from vacation, if the queue length is less than the minimum, they leave for another vacation in the first model, whereas in the second model they wait in the system until they get the minimum number of customers and then start servicing. The steady-state probability vector of the number of customers waiting and receiving service in unit I and waiting in the buffer is obtained for both the models, using the modified matrix geometric method. Numerical results are also presented.     

Combining a maintenance center M/M/c/m queue into the economic production quantity model with stochastic machine breakdowns and repair

This article considers a production system in which “m” identical machines produce nonidentical products at production rates. Products made by each machine are on the other hand consumed at a specific demand rate. Machines may be affected by unwanted breakdowns. Machines break down according to a Poisson distribution with equal rates and the failed machines are sent to maintenance center for repair which is consisted of “c” servers or servicemen. However, Number of machines is greater than number of servicemen (m > c). Hence, if the number of failed machines is greater than that of servicemen, the machines have to be put in a queue. Machines are put in one queue with the order of queue being FCFS. The queue has a typical M/M/c/m system. If machines are broken down during production, shortage will occur. This problem has been considered to obtain a single production cycle for the machines and an optimum number of the servers such that costs are minimized. For this purpose, distribution of waiting time for machines in repair center is calculated and a cost function is formed. Steepest descent and direct search methods are applied in this work to obtain optimal production cycle and maintenance servers, respectively. The proposed methods are studied using a comprehensive example.     

Two-server parallel system with pure space sharing and Markovian arrivals

We consider a parallel system with two identical servers and pure space sharing among rigid jobs. The parallel system is modeled as an MAP/M/2 queue with two types of jobs. While one type of jobs requires only one server, the other type needs both the servers before leaving the system. Using matrix–analytic methods, we analyze the queueing system in steady state. We report some interesting performance measures as well as illustrative examples to bring out the qualitative nature of the model under study.     

Combining a maintenance center M/M/c/m queue into the economic production quantity model with stochastic machine breakdowns and repair

This article considers a production system in which “m” identical machines produce nonidentical products at production rates. Products made by each machine are on the other hand consumed at a specific demand rate. Machines may be affected by unwanted breakdowns. Machines break down according to a Poisson distribution with equal rates and the failed machines are sent to maintenance center for repair which is consisted of “c” servers or servicemen. However, Number of machines is greater than number of servicemen (m > c). Hence, if the number of failed machines is greater than that of servicemen, the machines have to be put in a queue. Machines are put in one queue with the order of queue being FCFS. The queue has a typical M/M/c/m system. If machines are broken down during production, shortage will occur. This problem has been considered to obtain a single production cycle for the machines and an optimum number of the servers such that costs are minimized. For this purpose, distribution of waiting time for machines in repair center is calculated and a cost function is formed. Steepest descent and direct search methods are applied in this work to obtain optimal production cycle and maintenance servers, respectively. The proposed methods are studied using a comprehensive example.     

Optimal NT policies for M/G/1 system with a startup and unreliable server

This paper studies the control policies of an M/G/1 queueing system with a startup and unreliable server, in which the length of the vacation period is controlled either by the number of arrivals during the idle period, or by a timer. After all the customers are served in the queue exhaustively, the server immediately takes a vacation and operates two different policies: (i) the server reactivates as soon as the number of arrivals in the queue reaches to a predetermined threshold N or the waiting time of the leading customer reaches T units; and (ii) the server reactivates as soon as the number of arrivals in the queue reaches to a predetermined threshold N or T time units have elapsed since the end of the completion period. If the timer expires or the number of arrivals exceeds the threshold N, then the server reactivates and requires a startup time before providing the service until the system is empty. Furthermore, it is assumed that the server breaks down according to a Poisson process and his repair time has a general distribution. We analyze the system characteristics for each scheme. The total expected cost function per unit time is developed to determine the optimal thresholds of N and T at a minimum cost.     

On the multi-server retrial queue with geometric loss and feedback: computational algorithm and parameter optimization

We consider an M/M/c retrial queue with geometric loss and feedback. An arriving customer finding a free server enters into service immediately; otherwise the customer either enters into an orbit to try again after a random amount of time or leave the system without service. After the completion of service, he decides either to join the retrial orbit or to leave the system. The retrial system is modelled by a quasi-birth-and-death process, and some system performance measures are derived. The useful formulae for computing the rate matrix and stationary probabilities are derived by means of matrix-analytical approach. A cost model is derived to determine the optimal values of the number of servers and service rate simultaneously at the minimal total expected cost per unit time. Illustrative numerical examples demonstrate the optimization approach as well as the effect of various parameters on system performance measures.     

Analysis of an unobservable queue using arrival and departure times

Suppose one wants to assess the efficiency of a queueing system but is unable to observe directly its internal operations. This situation might arise if one works with a restricted set of historical data or because secrecy restricts access to the queueing facility. One might still be able to observe, from outside the system, the exact arrival and departure times of each customer. Using observations of arrival and departure times and knowledge of whether the service discipline is either first-come-first-served or last-come-first-served, one can exactly reconstruct the unobserved queue delays and service times of any sequence of arrivals during busy periods when the number of customers is greater than the number of servers. If the number of servers is also unknown, it too can be estimated. In this paper, we propose optimization models which determine the unknown number of servers.     

Analysis of a service center in a multiline factory

It has been demonstrated that several performance measures (e.g., expected delay and number in the system) improve when n servers take customers from a single queue rather than from n separate queues dedicated to individual servers. In this paper, we discuss the application of this concept in a manufacturing environment. In a multiple factory, common machines from individual lines were pooled to form a service center. The expected benefits, however, were not realized and we were called in to identify the cause of the poor performance. To analyze the service center, a Σ Gl/G/1 queueing model (the superposition of independent renewal arrival streams offered to a general single server) was used. We found that the material handling scheme in place significantly degraded the system performance. Using the model, alternative schemes were proposed to improve the performance of the facility.     

Priority tandem queueing model with admission control

A two-stage multi-server tandem queue with two types of processed customers is analyzed. The input is described by the Marked Markovian Arrival Process (MMAP). The first stage has an infinite number of servers while the second stage has a finite number of servers. The service time at the both stages has an exponential distribution. Priority customers are always admitted to the system. Non-priority customers are admitted to the system only if the number of busy servers at the second stage does not exceed some pre-assigned threshold. Queueing system’s behavior is described in terms of the multi-dimensional asymptotically quasi-Toeplitz continuous time Markov chain. It allows to exploit a numerically stable algorithm for calculation of the stationary distribution of the queueing system. The loss probability at the both stages of the tandem is computed. An economic criterion of the system operation is optimized with respect to the threshold. The effect of control on the main performance measures of the system is numerically demonstrated.     

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.     

具有两类请求的云计算中心服务器数量的优化

为提高云计算中心的服务质量,节约系统成本,针对具有两类用户请求的云计算中心,提出云计算中心的服务器数量的优化方案。首先,建立了具有两类用户请求的排队模型,分析系统的稳态概率分布、平均队长等性能指标;然后,建立了云计算中心的能耗模型;最后,联合系统的等待成本和能耗成本,构建系统的成本函数,对系统的服务器数量进行优化,从而使系统的成本最小。数值分析结果表明最优服务器数量是用户请求到达率的非减函数,为了使系统成本最小,云计算中心需要动态调整服务器的数量。     

Experiments with improved approximate mean value analysis algorithms

Approximate mean value analysis (MVA) is a popular technique for analyzing queueing networks because of the efficiency and accuracy that it affords. In this paper, we present a new software package, called the improved approximate mean value analysis library (IAMVAL), which can be easily integrated into existing commercial and research queueing network analysis packages. The IAMVAL packages include two new approximate MVA algorithms, the queue line (QL) algorithm and the fraction line (FL) algorithm, for analyzing multiple class separable queueing networks. The QL algorithm is always more accurate than, and yet has approximately the same computational efficiency as, the Bard–Schweitzer proportional estimation (PE) algorithm, which is currently the most widely used approximate MVA algorithm. The FL algorithm has the same computational cost and, in noncongested separable queueing networks where queue lengths are quite small, yields more accurate solutions than both the QL and PE algorithms.