Markovian queueing systems with retrials and heterogeneous servers

The asymptotic performances of a random access and an ordered entry G/M/K/Oqueueing system with a stationary counting arrival process, K heterogeneous parallel servers, no waiting room and retrials are approximated based on a two-parameter method. In a random access system, units upon arrival are randomly assigned to one of the servers. In an ordered entry system, servers are indexed from 1 to K, and units first arrive at server i and if the server is found to be busy, those units arrive at server (i + 1), for i = 1 to K − 1. In both queueing systems, if units are not processed by one of the servers, those units are not lost, instead they retry to receive service by merging with the incoming arrival units.

To approximate the asymptotic performance of the above queueing systems, a recursive algorithm is suggested, and appropriate performance measures are presented to be used as comparison criteria at the design stage. Furthermore, numerical results are provided and approximation outcomes are compared against those from a simulation study.     

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.     

Filtering of a semi-Markov queueing system with retrials

A recursive differential equation for the conditional probability of the number of waiting customers is derived for the M_wrM|G|1 queue with continuous monitoring of the server state.Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 169–173, July–August, 1991.     

Fuzzy control of queueing systems with heterogeneous servers

We consider the problem of optimal control of queueing systems with heterogeneous servers in parallel. The system objective is to assign customers dynamically to idle servers based on the state of the system so as to minimize the average cost of holding customers. Three cases, either known in the literature or new, are studied in detail: queueing systems with server heterogeneity in-service rates, in-service functions, and both in-service rates and in-service functions. An approach is presented using fuzzy control to solve these problems. Simulation shows that this approach is efficient and promising, especially in cases where analytical solutions do not exist     

On approximating the generalized occupancy of the G/M/K queueing system

The G/M/K is one of very few multiserver queueing systems for which analytical results exist. In 1951 Kendall [4] showed how to compute the steady-state probabilities of a G/M/K queueing system. Later, Takacs [6] suggested an iterative procedure for the evaluation of a needed component in Kendall's scheme; namely, the generalized occupancy ω^*. However, Takàcs' algorithm requires the computation of a general integral for each of its interations.In this paper we propose a simple and explicit approximation for the generalized occupancy of the G/M/K system. Several numerical results are also included.     

On performance characteristics for queueing systems with heterogeneous servers

The problem of optimal control for queueing system (QS) with heterogeneous servers was considering by many authors. In [8] it was shown that the optimal with respect to the number of jobs in the system minimization policy is a threshold type one and it obliges to use the fastest free server if necessary. However, calculation of performance characteristics under optimal policy and analysis of its preference before some other policies rest out of the investigators’ interests. The purpose of this paper is to analyze a multi-server heterogeneous exponential queue. We demonstrate the methods for the calculation of the steady-state probabilities and deriving the waiting and sojourn time distributions. Some performance characteristics of such a system under the optimal control policy are calculated and compared with the same characteristics for the model under other heuristic control policies, e.g., the usage of the Fastest Free Server (FFS) or Random Server Selection (RSS).     

The fokker-planck equation as an approximating formula for the G/M/K queueing system

In this paper we consider the problem of approximating the steady-state probabilities of the G/M/K queueing system. Although an analytical solution exists for the G/M/K system (see Kendall[5]), its explicit evaluation when dealing with general arrival processes imposes some computational difficulties. In this paper we propose an explicit and simple approximation which requires the knowledge of only the mean and variance of the interarrival-time rather than its full distributional form.     

Approximating the departure and the overflow processes from a G/G/K loss system

Both the departure and the overflow processes from a G/G/K loss system with generally distributed interarrival times, generally distributed service times, K parallel servers, no waiting room, and the random access processing discipline are approximated in steady state. Numerical results are provided and are compared against those from a simulation study.     

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.     

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.     

The optimal control of an M/G/1 queueing system with server vacations, startup and breakdowns

This paper studies the control policy of the N policy M/G/1 queue with server vacations, startup and breakdowns, where arrivals form a Poisson process and service times are generally distributed. The server is turned off and takes a vacation whenever the system is empty. If the number of customers waiting in the system at the instant of a vacation completion is less than N, the server will take another vacation. If the server returns from a vacation and finds at least N customers in the system, he requires a startup time before providing service until the system is again empty. It is assumed that the server breaks down according to a Poisson process and his repair time has a general distribution. The system characteristics of such a model are analyzed and the total expected cost function per unit time is developed to determine the optimal threshold of N at a minimum cost.     

Analysis of waiting time of M/G/1/K system with vacations under random scheduling and LCFS

This paper considers an M/G/1/K queueing system with multiple vacations under random scheduling and LCFS disciplines. As for M/G/1/K vacation models, Lee obtained the results of the joint distribution of the number of messages in the system and the remaining service or vacation time for a message. Using these expressions, we derive LSTs of the waiting time distribution under the two service disciplines. We show the calculation method for the first and the second moments of the waiting time under two service disciplines. Furthermore, we illustrate some numerical results of the mean waiting times and the coefficient of variations of the waiting time under FCFS, random scheduling and LCFS.     

带工作休假和工作故障的M/M/1/N排队系统性能分析

本文在可修M/M/1/N排队系统中引入了启动时间、工作休假和工作故障策略.在该系统中,服务台在休假期间不是完全停止工作,而是处于低速服务状态.设定服务台在任何时候均可发生故障,当故障发生时立刻进行维修.且当服务台在正规忙期出现故障时,服务台仍以较低的服务速率为顾客服务.服务台的寿命时间和修理时间均服从指数分布,且在不同...     

An MMAP/G/1 queueing system with repeated calls and with absolute priority

In this paper, a single-channel queueing system without an input buffer and with two types of requests is considered. At the input of the system, a marked Markov flow of requests arrives. Requests of the first type have absolute priority over requests of the second type; i.e., if a server is busy with servicing a request of the second type, an incoming request of the first type interrupts this servicing. Interrupted requests of the second type, as well as requests of this type that find the server busy on their arrival, become repeated requests and retry to get servicing later. An incoming first type request that finds the server busy with servicing a request of the same type is lost. The time of servicing requests has an arbitrary distribution dependent on the type of request. A nontrivial existence condition of the stationary operation of the system is obtained. A stationary probability distribution of system’s states at nested and random instants is found. Formulas for the main performance characteristics are obtained. The result of the numerical experiment is presented.     

Optimal addition of servers for a time-dependent queueing process

Necessary conditions for optimal control of systems containing a time delay that is a function of the state of the system and of time are derived by utilizing calculus of variations. The time delay may be in the state vector and in the control vector. The state vector and the control vector can be constrained by inequality constraints. A transformation to eliminate state variable inequality constraints by increasing the dimensions of state space, developed by Jacobson for an undelayed system, is extended to a system with time delays. Necessary conditions to obtain an optimal delay are shown, and an example of finding an optimal delay is included. A gradient algorithm for systems with state dependent time delays has been developed.     

Service and capacity allocation in M/G/c/c state-dependent queueing networks

The problem of service and capacity allocation in state-dependent M/G/c/c queueing networks is analyzed and algorithms are developed to compute the optimal allocation c. The model is applied to the modeling of pedestrian circulation systems and basic series, merge, and split topologies are examined. Also of interest are applications to problems of evacuation planning in buildings. Computational experiments assert the algorithm's speed, robustness, and effectiveness. The results obtained indicate that the pattern of the optimal capacity surprisingly repeats over different topologies and it is also heavily dependent upon the arrival rate. Additional computational simulation results are provided to show the accuracy of the approach in all configurations tested.     

Per-stream loss behavior of ∑MAP/M/1/K queuing system with a random early detection mechanism

In this paper, the matrix-analytic approach is applied to explore the per-stream loss behavior of the multimedia traffic under RED scheme. We constructed a ∑MAP/M/1/K queuing model for the RED mechanism with multimedia traffic which follows a continuous-time Markovian arrival process (MAP). In addition to evaluating the long-term per-stream packet drop probabilities, we examine the bursty nature of per-stream packet drops by means of conditional statistics with respect to dropped periods and the probability that the queuing system stays in the dropped period. The dropped period corresponds to having more than a certain number of packets in router buffer; non-dropped period corresponds to the opposite. These performance measures describe the quality of service provided by the router to particular multimedia traffic streams in the presence of background multimedia traffic.