Analysis of a G/M/K/O queueing loss system with heterogeneous servers and retrials

Consider a G/M/K/O queueing loss system with K heterogeneous servers, exponentially distributed service times, no waiting room, a stationary counting arrival process, and an ordered entry. The ordered entry rule implies that, if the servers are indexed from 1 to K, units first arrive at the first server, then at the second server, and finally at the Kth server. In this queueing system, units that find the servers busy are not lost. Those units re-try to receive service by merging with the incoming units to be reconsidered for service by one of the free servers. This queueing system is analysed in terms of approximating the flows of units inside the system by a two parameter method. An example is introduced and approximation results are compared with those from a simulation study.     

Cost-minimization analysis of a working vacation queue with N-policy and server breakdowns

This paper investigates the N-policy M/M/1 queueing system with working vacation and server breakdowns. As soon as the system becomes empty, the server begins a working vacation. The server works at a lower service rate rather than completely stopping service during a vacation period. The server may break down with different breakdown rates during the idle, working vacation, and normal busy periods. It is assumed that service times, vacation times, and repair times are all exponentially distributed. We analyze this queueing model as a quasi-birth–death process. Furthermore, the equilibrium condition of the system is derived for the steady state. Using the matrix-geometric method, we find the matrix-form expressions for the stationary probability distribution of the number of customers in the system and system performance measures. The expected cost function per unit time is constructed to determine the optimal values of the system decision variables, including the threshold N and mean service rates. We employ the particle swarm optimization algorithm to solve the optimization problem. Finally, numerical results are provided, and an application example is given to demonstrate the applicability of the queueing model.     

Comparative analysis of a randomized N-policy queue: An improved maximum entropy method

We analyze a single removable and unreliable server in an M/G/1 queueing system operating under the 〈p, N〉-policy. As soon as the system size is greater than N, turn the server on with probability p and leave the server off with probability (1 ? p). All arriving customers demand the first essential service, where only some of them demand the second optional service. He needs a startup time before providing first essential service until there are no customers in the system. The server is subject to break down according to a Poisson process and his repair time obeys a general distribution. In this queueing system, the steady-state probabilities cannot be derived explicitly. Thus, we employ an improved maximum entropy method with several well-known constraints to estimate the probability distributions of system size and the expected waiting time in the system. By a comparative analysis between the exact and approximate results, we may demonstrate that the improved maximum entropy method is accurate enough for practical purpose, and it is a useful method for solving complex queueing systems.     

Control Policies of an M/G/1 Queueing System with a Removable and Non-reliable Server

This paper considers a single non-reliable server in the ordinary M/G/1 queueing system whose arrivals form a Poisson process and service times are generally distributed. We also study a single removable and non-reliable server in the controllable M/G/1 queueing systems operating under the N policy, the T policy and the Min( N , T ) policy. It is assumed that the server breaks down according to a Poisson process and the repair time has a general distribution. In three control policies, we show that the probability that the server is busy in the steady-state is equal to the traffic intensity. It is shown that the optimal N policy and the optimal Min( N , T ) policy are always superior to the optimal T policy. Sensitivity analysis is also investigated.     

Queueing-model based analysis of assembly lines with finite buffers and general service times

In this paper, we study the production process on multi-stage assembly lines. These production systems comprise simple processing as well as assembly stations. At the latter, workpieces from two or more input stations have to be merged to form a new one for further processing. As the flow of material is asynchronous with stochastic processing times at each station, queueing effects arise as long as buffers provide waiting room. We consider finite buffer capacities and generally distributed processing times. Processing is a service operation to customer items in the sense of a queueing system. The arrival stream of customer items is generated by processing parts at a predecessor station. This paper describes an approximation procedure for determining the throughput of such an assembly line. Exact solutions are not available in this case. For performance evaluation, a decomposition approach is used. The two-station subsystems are analyzed by G/G/1/N$G/G/1/N$ stopped-arrival queueing models. In this heuristic approach, the virtual arrival and service rates, and the squared coefficients of variation of these subsystems are determined. A system of decomposition equations which are solved iteratively is presented. Any solution to this system of equations indicates estimated values for the subsystems’ unknown parameters. The quality of the presented approximation procedure is tested against the results of various simulation experiments.     

A pseudoconservation law for a time-limited service polling system with structured batch poisson arrivals

We consider a cyclic-service queueing system (polling system) with time-limited service, in which the length of a service period for each queue is controlled by a timer, i.e., the server serves customers until the timer expires or the queue becomes empty, whichever occurs first, and then proceeds to the next queue. The customer whose service is interrupted due to the timer expiration is attended according to the nonpreemptive service discipline. For the cyclic-service system with structured batch Poisson arrivals (M^x/G/1) and an exponential timer, we derive a pseudoconservation law and an exact mean waiting time formula for the symmetric system.     

Higher-order distributional properties in closed queueing networks

In many real-life computer and networking applications, the distributions of service times, or times between arrivals of requests, or both, can deviate significantly from the memoryless negative exponential distribution that underpins the product-form solution for queueing networks. Frequently, the coefficient of variation of the distributions encountered is well in excess of one, which would be its value for the exponential. For closed queueing networks with non-exponential servers there is no known general exact solution, and most, if not all, approximation methods attempt to account for the general service time distributions through their first two moments.We consider two simple closed queueing networks which we solve exactly using semi-numerical methods. These networks depart from the structure leading to a product-form solution only to the extent that the service time at a single node is non-exponential. We show that not only the coefficients of variation but also higher-order distributional properties can have an important effect on such customary steady-state performance measures as the mean number of customers at a resource or the resource utilization level in a closed network.Additionally, we examine the state that a request finds upon its arrival at a server, which is directly tied to the resulting quality of service. Although the well-known Arrival Theorem holds exactly only for product-form networks of queues, some approximation methods assume that it can be applied to a reasonable degree also in other closed queueing networks. We investigate the validity of this assumption in the two closed queueing models considered. Our results show that, even in the case when there is a single non-exponential server in the network, the state found upon arrival may be highly sensitive to higher-order properties of the service time distribution, beyond its mean and coefficient of variation.This dependence of mean numbers of customers at a server on higher-order distributional properties is in stark contrast with the situation in the familiar open M/G/1 queue. Thus, our results put into question virtually all traditional approximate solutions, which concentrate on the first two moments of service time distributions.     

Filtering effects of queueing systems on end-to-end network performance

A network is a mesh connection of network elements (NEs), each of which can be characterized as a single server queueing system. Upon arrival to the single server queueing system, a customer may see another customer already in service, and yet others may be in the queue. The new arrival either joins the queue, or is lost if there is no room available. By studying the traffic parameters at the ingress and egress of a generic NE, it is possible to deduce the filtering effect of a single server queueing system. On the assumption of exponential on–off traffic flows, we have derived equations to recursively compute the output traffic parameters as a function of the input traffic parameters. Since the output from the ith NE is also the input to the (i+1)st NE, the recursive equations allow us to assess the end-to-end network performance. Simulation results are used to gauge the accuracy of the analytical approach.     

On the existence of periodic behaviour of switched linear systems

A heuristic algorithm is suggested for approximating the departure process from a G/M/1 queueing system with generally distributed interarrival times, a single markovian server, an infinite capacity, and the first-come first-served queueing discipline, in the steady state. The tandem behaviour of the system is then approximated in the steady state. Finally, the approximation results are compared against both a simulation study and the approximation results of Kuehn (1979) and Whitt (1983 a, b).     

A repairable queueing model with two-phase service,start-up times and retrial customers

A repairable queueing model with a two-phase service in succession, provided by a single server, is investigated. Customers arrive in a single ordinary queue and after the completion of the first phase service, either proceed to the second phase or join a retrial box from where they retry, after a random amount of time and independently of the other customers in orbit, to find a position for service in the second phase. Moreover, the server is subject to breakdowns and repairs in both phases, while a start-up time is needed in order to start serving a retrial customer. When the server, upon a service or a repair completion finds no customers waiting to be served, he departs for a single vacation of an arbitrarily distributed length. The arrival process is assumed to be Poisson and all service and repair times are arbitrarily distributed. For such a system the stability conditions and steady state analysis are investigated. Numerical results are finally obtained and used to investigate system performance.     

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.     

Optimal management for infinite capacity N-policy M/G/1 queue with a removable service station

In this article, we consider an infinite capacity N-policy M/G/1 queueing system with a single removable server. Poisson arrivals and general distribution service times are assumed. The server is controllable that may be turned on at arrival epochs or off at service completion epochs. We apply a differential technique to study system sensitivity, which examines the effect of different system input parameters on the system. A cost model for infinite capacity queueing system under steady-state condition is developed, to determine the optimal management policy at minimum cost. Analytical results for sensitivity analysis are derived. We also provide extensive numerical computations to illustrate the analytical sensitivity properties obtained. Finally, an application example is presented to demonstrate how the model could be used in real applications to obtain the optimal management policy.     

Sensitivity analysis of the optimal management policy for a queuing system with a removable and non-reliable server

The management policy of an M/G/1 queue with a single removable and non-reliable server is considered. The decision-maker can turn the single server on at any arrival epoch or off at any service completion. It is assumed that the server breaks down according to a Poisson process and the repair time has a general distribution. Arrivals form a Poisson process and service times are generally distributed. In this paper, we consider a practical problem applying such a model. We use the analytic results of the queueing model and apply an efficient Matlab program to calculate the optimal threshold of management policy and some system characteristics. Analytical results for sensitivity analysis are obtained. We carry out extensive numerical computations for illustration purposes. An application example is presented to display how the Matlab program could be used. The research is useful to the analyst for making reliable decisions to manage the referred queueing system.     

Analysis of a class of distributed queues with applications

Recently we have developed a class of media access control algorithms for different types of Local Area Networks. A common feature of these LAN algorithms is that they represent various methods by which the processors in the LAN can simulate the availability of centralized packet transport facility, but whose service incorporates a particular type of changeover time known as ‘moving server’ overhead. First we describe the operation of moving server systems in general, for both First-Come-First-Served and Head-of-the-Line orders of service, together with an approach for their delay analysis where we transform the moving server system into a conventional queueing system having proportional waiting times. Then we describe how the various LAN algorithms may be obtained from the ideal moving server system, and how a major component of their performance characteristics is determined by the performance characteristics of that ideal system. Finally, we evaluate the compatibility of such LAN algorithms with separable queueing network models of distributed systems by computing the interdeparture time distribution for M/M/1 in the presence of moving server overhead. Although it is not exponential except in the limits of low server utilization or low overhead, the interdeparture time distribution is a weighted sum of exponential terms with a coefficient of variation not much smaller than unity. Thus, we conjecture that a service centre with moving server overhead could be used to represent one of these LAN algorithms in a product form queueing network model of a distributed system without introducing significant approximation errors.     

Stationary distributions and optimal control of queues with batch Markovian arrival process under multiple adaptive vacations

We consider an infinite-buffer single server queue with batch Markovian arrival process (BMAP) and exhaustive service discipline under multiple adaptive vacation policy. That is, the server serves until system emptied and after that server takes a random maximum number H different vacations until either he finds at least one customer in queue or the server have exhaustively taken all the vacations. The maximum number H of vacations taken by the server is a discrete random variable. We obtain queue-length distributions at various epochs such as, service completion/vacation termination, pre-arrival, arbitrary, post-departure and pre-service. The proposed analysis is based on the use of matrix-analytic procedure to obtain queue-length distribution at a post-departure epoch. Later we use supplementary variable method and simple algebraic manipulations to obtain the queue-length distribution at other epochs using queue-length distribution at post-departure epoch. Some important performance measures, like mean queue lengths and mean waiting times have been obtained. Several other vacation queueing models can be obtained as a special case of our model, e.g., single-, multiple-vacation model and queues with exceptional first vacation time. Finally, the total expected cost function per unit time is considered to determine a locally optimal multiple adaptive vacation policy at a minimum cost.     

k-out-of-n: G system with repair: the D-policy

In this paper we consider a k-out-of-n: G system with repair under D-policy. According to this policy whenever the workload exceeds a threshold D a server is called for repair and starts repair one at a time. He is sent back as soon as all the failed units are repaired. The repaired units are assumed to be as good as new. The repair time and failure time distributions are assumed to be exponential. We obtain the system state distribution, system reliability, expected length of time the server is continuously available, expected number of times the system is down in a cycle and several other measures of performance. We compute the optimal D value which maximizes a suitably defined cost function.Scope and purposeThis paper considers a repair policy, called D-policy, of a k-out-of-n: G system. In a k-out-of-n: G system, the system functions as long as there are atleast k operational units. The server activation cost is high once it becomes idle due to all failed units repaired. Hence it is activated when the accumulated amount of work reaches D. This paper examines the optimal D-value by bringing in costs such as the cost of system being down, the server activation cost. Activating the server the moment the first failure takes place may involve very heavy fixed cost per cycle (a cycle is the duration from a point at which the server becomes idle to the next epoch at which it becomes idle after being activated). The other extreme of server activation only after n−k+1 units fail leads to the system being down for a long duration in each cycle. Hence the need for the optimal D-policy. A brief account of k-out-of-n: G system can be had in Ross (Ross, SM. Introduction to probability models, 6th ed., New York: Academic Press, 1997). The results obtained here find direct applications in reliability engineering, Production systems, Satellite communication, etc.     

T-preemptive priority queue and its application to the analysis of an opportunistic spectrum access in cognitive radio networks

We propose a new priority discipline called the T-preemptive priority discipline. Under this discipline, during the service of a customer, at every T time units the server periodically reviews the queue states of each class with different queue-review processing times. If the server finds any customers with higher priorities than the customer being serviced during the queue-review process, then the service of the customer being serviced is preempted and the service for customers with higher priorities is started immediately. We derive the waiting-time distributions of each class in the M/G/1 priority queue with multiple classes of customers under the proposed T-preemptive priority discipline. We also present lower and upper bounds on the offered loads and the mean waiting time of each class, which hold regardless of the arrival processes and service-time distributions of lower-class customers. To demonstrate the utility of the T-preemptive priority queueing model, we take as an example an opportunistic spectrum access in cognitive radio networks, where one primary (licensed) user and multiple (unlicensed) users with distinct priorities can share a communication channel. We analyze the queueing delays of the primary and secondary users in the proposed opportunistic spectrum access model, and present numerical results of the queueing analysis.     

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.     

The interdeparture time distribution for each class in the ∑Mi/Gi/1 queue with set-up times and repeated server vacations

This paper studies the interdeparture time distribution of one class of customers who arrive at a single server queue where customers of several classes are served and where the server takes a vacation whenever the system becomes empty or is empty when the server returns from a vacation. Furthermore, the first customer in the busy period is allowed to have an exceptional service time (set-up time), depending on the class to which this customer belongs. Batches of customers of each class arrive according to independent Poisson processes and compete with each other on a FIFO basis. All customers who belong to the same class are served according to a common generally distributed service time. Service times, batch sizes and the arrival process are all assumed to be mutually independent. Successive vacation times of the server form independent and identically distributed sequences with a general distribution.For this queueing model we obtain the Laplace transform of the interdeparture time distribution for each class of customers whose batch size is geometrically distributed. No explicit assumptions of the batch size distributions of the other classes of customers are necessary to obtain the results.The paper ends by showing how the mathematical results can be used to evaluate a protocol that controls access to a shared medium of an ATM passive optical network. The numerical results presented in the last section of this paper show that the bundle spacing principle that is used by the permit distribution algorithm of this protocol introduces high delays and in many cases also more variable interdeparture times for the ATM cells of individual connections. An alternative algorithm is proposed that does not cope with these performance short comings and at the same time conserves the good properties of the protocol.     

Reducing congestion in bulk-service finite-buffer queueing system using batch-size-dependent service

In the design and analysis of any queueing system, one of the main objectives is to reduce congestion which can be achieved by controlling either arrival-rates or service-rates. This paper adopts the latter approach and analyzes a single-server finite-buffer queue where customers arrive according to the Poisson process and are served in batches of minimum size a with a maximum threshold limit b. The service times of the batches are arbitrarily distributed and depends on the size of the batches undergoing service. We obtain the joint distribution of the number of customers in the queue and the number with the server, and distributions of the number of customers in the queue, in the system, and the number with the server. Various performance measures such as the average number of customers in the queue (system) and with the server etc. are obtained. Several numerical results are presented in the form of tables and graphs and it is observed that batch-size-dependent service rule is more effective in reducing the congestion as compared to the one when service rates of the batches remain same irrespective of the size of the batch. This model has potential application in manufacturing, computer-communication network, telecommunication systems and group testing.