A hybrid method for performance analysis of G/G/m queueing networks

Open queueing networks are useful for the performance analysis of numerous real systems. Since exact results exist only for a limited class of networks, decomposition methods have been extensively used for approximate analysis of general networks. This procedure is based on several approximation steps. Successive approximations made in this approach can lead to a considerable error in the output. In particular, there are no general accurate formulas for computing the mean waiting time and the inter-departure variance in general multiple-server queues. This causes the results from decomposition methods when applied to G/G/m queueing networks to be very approximative and to significantly deviate from actual performance values. We suggest substituting some approximate formulae by low-cost simulation estimates in order to obtain more accurate results when benefiting from the speed of an analytical method. Numerical experiments are presented to show that the proposed approach provides improved performance.     

Properties and performance modelling of finite buffer M/G/1/K networks

Finite buffer, single-server queueing systems and networks are difficult to analyze since the length of time a customer spends in the system does not follow the Markovian property. A two-moment approximation schema is developed for the probability distribution of M/G/1/K systems and extended to the analysis of M/G/1/K   queueing networks. The general purpose of this paper is to develop a flexible and practical transform-free approach for computing the probability distribution and performance measures of the system as well as identify the underlying properties of these systems. It is shown that for most performance measures, a sigmoid or S-shaped curve with an inflection point at ρ=1$\rho =1$ appears as K→∞$K\to \infty$. This has direct implications for the analysis and optimization of such systems. The performance modelling of the M/G/1/K queueing networks of general topologies along with extensive numerical results accompany the paper along with the linear concave performance measures for these systems.     

Optimal policies for a controlled queueing system with removable server under a random vacation circumstance

In this paper, we consider two stochastic models for a controlled single-server M/G/1 queueing system under a random vacation circumstance. The relevant expected costs are formulated under two control strategies and approximated by means of a familiar diffusion approximation method. Numerical calculations are devoted to examine the accuracy of the proposed approximation method. The results show that the diffusion approximation method is reasonably good for the performance evaluation on the typical queueing control systems, especially, for the M/M/1 single-server queue.     

Single server stochastic recirculation systems

A recursive methodology is suggested for approximating the asymptotic performance of a single server recirculation system. A single server recirculation system is modeled by a G/G/1/0 queueing loss system with generally distributed interarrivai times, generally distributed service times, a single server, no waiting room, first come first served queueing discipline, and retrials. In this queueing system, the units which initially are not processed by the server are not lost. These units retry to receive service by retrying. Furthermore, numerical results are provided and the approximation outcomes are compared against those from a simulation study.     

Throughput analysis for order picking system with multiple pickers and aisle congestion considerations

Most of previous studies in picker-to-parts warehousing systems investigated only single-picker operations and are therefore adequate to evaluate order picking efficiency by travel distance as aisle congestion never takes place in such systems. In real world applications, the congestion inevitably occurs when a system has multiple pickers working together within the same region. This paper presents an approximation method based on a GI/G/1 closed queueing network by using self-correcting approximation technique algorithm to evaluate the throughput time of an order picking system with multiple pickers and aisle congestion considerations for different routing policies. The results generated by the proposed method are compared and validated via simulation model using eM-plant simulator for different sizes of warehouses. The results indicate that the approximation method appears to be sufficiently accurate for practical purposes. The sensitivity analysis of the throughput time with respect to order sizes, number of pickers and number of aisles are conducted and the performance of different item storage policies are also evaluated using the proposed approximation model.     

Information theoretic analysis for a general queueing system at equilibrium with application to queues in tandem

Summary In this paper, information theoretic inference methology for system modeling is applied to estimate the probability distribution for the number of customers in a general, single server queueing system with infinite capacity utilized by an infinite customer population. Limited to knowledge of only the mean number of customers and system equilibrium, entropy maximization is used to obtain an approximation for the number of customers in the G¦ G¦1 queue. This maximum entropy approximation is exact for the case of G=M, i.e., the M¦M¦1 queue. Subject to both independent and dependent information, an estimate for the joint customer distribution for queueing systems in tandem is presented. Based on the simulation of two queues in tandem, numerical comparisons of the joint maximum entropy distribution is given. These results serve to establish the validity of the inference technique and as an introduction to information theoretic approximation to queueing networks.This work was supported under a Naval Research Laboratory Fellowship under Grant N00014-83G-0203 and under an ONR Grant N00014-84K-0614 Former address:Westinghouse Defense and Electronics Center, Baltimore, MD, USA     

The BMAP/PH/N retrial queueing system operating in Markovian random environment

We consider the BMAP/PH/N retrial queueing system operating in a finite state space Markovian random environment. The stationary distribution of the system states is computed. The main performance measures of the system are derived. Presented numerical examples illustrate a poor quality of the approximation of the main performance measures of the system by means of the simpler queueing models. An effect of smoothing the traffic and an impact of intensity of retrials are shown.     

Existence and uniqueness of nonnegative solution of M/GB/1 queueing model

In this paper, we set up M/G^B/1 queueing model as an abstract Cauchy problem and prove the existence of a unique positive solution using the theory of strongly continuous semigroups of operators.     

Direct martingale arguments for stability: The M|G|1 case

A direct martingale argument is given for studying stability properties of the simple M|G|1 queueing system. The technique is of independent interest and can be used elsewhere.     

The AMVA priority approximation

Most computer systems contain one or more system resources whose usage is controlled on the basis of workload priorities. Unfortunately, the exact analysis of queueing network models incorporating priority scheduling disciplines is usually infeasible. The MVA Priority Approximation has been proposed as a comparatively inexpensive, and yet reasonably accurate, approximation technique for queueing networks with priority scheduled service centers. Even this algorithm, however, is too expensive to apply to large networks with many classes of customers.In this paper, we show how the MVA Priority Approximation can be modified so that it utilizes approximate rather than exact Mean Value Analysis (MVA), without significant loss of accuracy. Extensive numerical experiments are performed to further assess the accuracy of the modified algorithm, termed here the AMVA Priority Approximation. These experiments utilize the parameter space mapping technique for studying ‘local’ queueing network approximations.     

An M/G/C/C state-dependent network simulation model

A discrete-event digital simulation model is developed to study traffic flows in M/G/C/C state-dependent queueing networks. Several performance measures are evaluated, namely (i) the blocking probability, (ii) throughput, (iii) the expected number of the customers in the system, and (iv) expected travel (service) time. Series, merge, and split topologies are examined with special application to pedestrian planning evacuation problems in buildings. Extensive computational experiments are presented showing that the simulation model is an effective and insightful tool to validate analytical expressions and also to analyze general accessibility in network evacuation problems especially in high-rise buildings.     

Approximating queue lengths inM(t)/G/1 queue using the maximum entropy principle

Using the discrete time approach a model is developed for obtaining the expected queue length of theM(t)/G/1 queue. This type of queue occurs in different forms in transportation and traffic systems and in communications and manufacturing systems. In order to cut down the very high computational efforts required to evaluate the performance measures in such queues by exact methods, the Maximum Entropy Principle is used to approximate the expected queue length which is one of the most commonly used performance measures. A procedure is then developed for reducing the error encountered when this approximation is adopted. The results from this paper will encourage the practitioners to use the appropriate time-varying queueing models when the need arises instead of resorting to very poor approximations.     

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.     

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.     

Randomized control of T-policy for an M/G/1 system

We study an M/G/1 queueing system with a server that can be switched on and off. The server can take a vacation time T after the system becomes empty. In this paper, we investigate a randomized policy to control a server with which, when the system is empty, the server can be switched off with probability p and take a vacation or left on with probability (1 − p) and continue to serve the arriving customers. For this system, we consider the operating cost and the holding cost where the operating cost consists of the system running and switching costs (start up and shut down costs). We describe the structure and characteristics of this policy and solve a constrained problem to minimize the average operating cost per unit time under the constraint for the holding cost per unit time.     

On the number of customers served in the M/G/1 retrial queue: first moments and maximum entropy approach

In this paper we present general results on the number of customers, I, served during the busy period in an M/G/1 retrial system. Its analysis in terms of Laplace transforms has been previously discussed in the literature. However, this solution presents important limitations in practice; in particular, the moments of I cannot be obtained by direct differentiation. We propose a direct method of computation for the second moment of I and also for the probability of k,k⩽4, customers being served in a busy period. Then, the maximum entropy principle approach is used to estimate the true distribution of I according to the available information.Scope and purposeWe consider an M/G/1 queue with retrials. Retrial queueing systems are characterized by the fact that, an arriving customer who finds the server busy is obliged to leave the service area and return later to repeat his request after some random time. We deal with I, the number of customers served during the busy period of a retrial queue, and obtain closed expressions for its main characteristics, which will be employed in order to estimate the true distribution of this random variable.     

Switched poisson process/g/1 queue with service interruptions

In this paper, we develop an expression for the expected waiting time in a single server queueing system subject to interruptions with alternately varying Poisson arrival and renewal service rates. This queueing system is useful to model situations in production, computer and telecommunication systems in which customer arrivals and service requirements differ depending on whether the server is working or not. We develop an expression for the expected waiting time by approximating the virtual delay process by a Brownian motion. Our approximation for the expected waiting time involves only the means and variances and does not depend on any assumptions regarding the interarrival, service or switching time distributions. We present simulation results to illustrate the quality of our approximations.     

Blending randomness in closed queueing network models

Random environments are stochastic models used to describe events occurring in the environment a system operates in. The goal is to describe events that affect performance and reliability such as breakdowns, repairs, or temporary degradations of resource capacities due to exogenous factors. Despite having been studied for decades, models that include both random environments and queueing networks remain difficult to analyse. To cope with this problem, we introduce the blending algorithm, a novel approximation for closed queueing network models in random environments. The algorithm seeks to obtain the stationary solution of the model by iteratively evaluating the dynamics of the system in between state changes of the environment. To make the approach scalable, the computation relies on a fluid approximation of the queueing network model. A validation study on 1800 models shows that blending can save a significant amount of time compared to simulation, with an average accuracy that grows with the number of servers in each station. We also give an interpretation of this technique in terms of Laplace transforms and use this approach to determine convergence properties.     

Approximating nonstationary ph(t)⧸ph(t)⧸1⧸c queueing systems

A state space partitioning and surrogate distribution approximation (SDA) approach for analyzing the time-dependent behavior of queueing systems is described for finite-capacity, single server queueing systems with time-dependent phase arrival and service processes. Regardless of the system capacity, c, the approximation requires the numerical solution of only k₁ + 3k₁k₂ differential equations, where k₁ is the number of phases in the arrival process and k₂ is the number of phases in the service process, compared to the k₁ + ck₁ k₂ Kolmogorov-forward equations required for the classic method of solution. Time-dependent approximations of mean and standard deviation of the number of entities in the system are obtained. Empirical test results over a wide range of systems indicate that the approximation is extremely accurate.     

Pruning 2-Connected Graphs

Given an undirected graph G with edge costs and a specified set of terminals, let the density of any subgraph be the ratio of its cost to the number of terminals it contains. If G is 2-connected, does it contain smaller 2-connected subgraphs of density comparable to that of?G? We answer this question in the affirmative by giving an algorithm to pruneG and find such subgraphs of any desired size, incurring only a logarithmic factor increase in density (plus a small additive term). We apply our pruning techniques to give algorithms for two NP-Hard problems on finding large 2-vertex-connected subgraphs of low cost; no previous approximation algorithm was known for either problem. In the k-2VC problem, we are given an undirected graph G with edge costs and an integer k; the goal is to find a minimum-cost 2-vertex-connected subgraph of G containing at least k vertices. In the Budget-2VC problem, we are given a graph G with edge costs, and a budget B; the goal is to find a 2-vertex-connected subgraph H of G with total edge cost at most B that maximizes the number of vertices in H. We describe an O(log?nlog?k) approximation for the k-2VC problem, and a bicriteria approximation for the Budget-2VC problem that gives an $O(\frac{1}{\epsilon}\log^{2} n)$ approximation, while violating the budget by a factor of at most 2+ε.