Throughput bounds for closed queueing networks

Analytical lower and upper bounds for the throughput of closed queueing networks with single and delay (infinite) servers are studied in this paper. The numerical evaluation of these bounds requires a small number of significant operations which is independent of the population N. This is in contrast to the exact computation of the throughput which requires at least O(N) operations as N tends to infinity. The bounds are given by simple closed-form analytical expressions and may be more suitable for various performance studies than the algorithmical form of the exact solution.In this paper, the previously known balanced-job bounds are generalized to networks containing delay servers (terminals) and a hierarchy of bounds is obtained for single and multiple class networks. For the single class network, further new bounds are derived: lower and upper bounds that require the evaluation of one square root and an upper bound that requires a constant number of exponentiations. This upper bound does not employ the balancing of server loadings and is especially useful for asymptotic analysis in the case of a large number of customers N.     

Mean-value analysis and convolution method for queue-dependent servers in closed queueing networks

In this paper, we formulate a recursive relation for the marginal probabilities of a closed network with K customers in terms of the same network with K ? 1 customers. Mean-value analysis (MVA) is an application of this relation, together with Little's formula. It is shown that the convolution method, too, can be based on the same recursive result. This leads to a new convolution algorithm called normalized convolution algorithm (NCA), which like MVA works entirely with probabilities and throughputs rather than with quantities such as normalization contacts. NCA avoids a difficult problem, the occurrence of floating-point over-flows in the original convolution algorithm.We shall also solve a numerical stability problem found in MVA. Finally, we show how MVA and the convolution algorithm can be combined in the same problem to yield a hybrid method retaining the best properties of both methods.     

Modelling congestion in closed queueing networks

We will consider the problem of identifying regions of congestion in closed queueing networks with state-dependent service rates. A particular queue will be called a bottleneck if the number of customers in that queue grows without bound as the total number of customers in the network becomes large. We will review methods for identifying potential bottlenecks, with a view to controlling congestion. We will see that the problem of identifying bottlenecks can be reduced to one of finding them in an isolated subnetwork with suitably modified routing intensities. Several special cases will be studied, illustrating a range of behaviour. For example, it is possible for a subnetwork to be congested, yet each queue in that subnetwork is not strictly a bottleneck.     

An approximation method for a class of queueing systems

We consider a queueing system with an ordered hunt. Specifically, we consider a communication system in which messages arrive at a node that has n output links numbered 1,…,n, and an arriving message is processed by the lowest numbered idle link. Obtaining such steady-state parameters as the expected delay of an arbitrary message and the utilization factor of each link requires knowledge of the complete state space of the system and the solution of 2ⁿ linear equations. In this paper we develop a method of computing the approximate values of these parameters without the need for the knowledge of the complete state space and the solution of 2ⁿ linear equations.     

Equivalencies between open and closed queueing networks with finite buffers

Equivalencies between open and closed models of queueing networks with finite buffers are investigated. Interarrival times in open networks and service times are assumed to be exponentially distributed. Using these equivalencies, bounds on the throughput of open networks are established.     

Structured priority queueing systems with applications to packet-radio networks

In this paper we investigate a certain class of systems containing dependent discrete time queues. This class of systems consists of N nodes transmitting packets to each other or to the outside of the system over a common shared channel, and is characterized by the fact that access to the channel is assigned according to priorities that are preassigned to the nodes. To each node a given probability distribution is attached, that indicates the probabilities that a packet transmitted by the node is forwarded to one of the other nodes or to the outside of the system.

Using extensively the fact that the joint generating function of the queue lengths distribution is an analytic function in a certain domain, we obtain an expression for this joint generating function. From the latter any moment of the queue lengths and also average time delays can be obtained.

The main motivation for investigating the class of systems of this paper is its applicability to several packet-radio networks. We give two examples: The first is a certain access scheme for a network where all nodes can hear each other, and the second is a three-node tandem packet-raido network.     

Modeling and analysis of closed loop manufacturing systems using parameter coupling

Closed loop manufacturing systems (CLMSs) with recirculating material handling devices are extensively used in various industrial environments. The performance of such systems is impacted by many factors such as the total capacity of pallets, the actual number of pallets in the system, the machine reliability and processing time, the pallet index speed, and the positions of loading/unloading points. These factors make the accurate analysis and optimization of complex CLMSs very difficult and challenging. This paper presents a new parameter coupling technique to model and analyze a wide range of CLMSs. It is an enhancement based on the existing open production line analysis with unreliable assembly machines and finite buffers. Virtual assembly machines are introduced to represent the specific phenomena of CLMSs such as the recirculation of empty pallets and the sharing of conveyor space. Two types of parameter coupling patterns, the machine parameter coupling, and the buffer capacity coupling, are introduced to reflect the characteristics of the CLMSs. The parameter coupling technique is simple and effective for analyzing a broad range of CLMSs. Comparisons between this analytic method and simulation experiments demonstrate that the proposed parameter coupling technique is fast, accurate and robust.     

Response time sensitivity measurement for computer systems and general closed queuing networks

A method is described for measuring the performance sensitivity variable $\text{S = (}\text{?T}\text{?μ}\text{) (}\text{μ}\text{T}\text{)}$ when T is a mean response time and μ is the processing rate of one device in a computer system, or one server in a closed or partly open queuing network. The derivative is with respect to a hypothetical change in μ, in a system operating on the identical job sequence. The measurement method is basically an algorithm for reducing operating data, and can be applied to statistically nonstationary systems, for which repeated experiments are difficult to interpret. No previous work on these lines is known to the author. The paper introduces the derivative $\text{?T}\text{?μ}$, shows it exists and describes an algorithm to obtain it; demonstrates it on simulated data; describes and tests an approximation, and briefly investigates the sampling error of S. The measured values show insignificant bias and are close to expected theoretical values computed from analytic queuing models.     

A generalized method of moments for closed queueing networks

We introduce a new solution technique for closed product-form queueing networks that generalizes the Method of Moments (MoM), a recently proposed exact algorithm that is several orders of magnitude faster and memory efficient than the established Mean Value Analysis (MVA) algorithm. Compared to MVA, MoM recursively computes higher-order moments of queue lengths instead of mean values, an approach that remarkably reduces the computational costs of exact solutions, especially on models with large numbers of jobs.In this paper, we show that the MoM recursion can be generalized to include multiple recursive branches that evaluate models with different numbers of queues, a solution approach inspired by the Convolution algorithm. Combining the approaches of MoM and Convolution simplifies the evaluation of normalizing constants and leads to large computational savings with respect to the recursive structure originally proposed for MoM.     

Computational aspects of aggregation in multiple class queueing networks

We extend the convolution and mean value analysis algorithms to incorporate composite servers that result from the aggregation of stations in a multiple class queueing network model. The method defines a new composite server device factor that is used in the product form solution of the aggregated network. The approximate analysis of multiclass networks can then be handled in a computationally efficient manner provided that a sufficient condition is satisfied.     

An analysis of an approximation algorithm for queueing networks

Queueing network models have proved to be useful aids in computer system performance prediction. Numerous approximation algorithms have been devised to allow queueing networks to be analyzed with a reduced computational expense. In particular, for separable queueing networks several popular iterative approximation algorithms are available.

One disadvantage of these algorithms has been the lack of results concerning their behavior, such as whether or not iteration convergence is guaranteed. This paper presents an analysis of an approximate MVA algorithm proposed by Schweitzer (1979). It is proved that the equations defining the algorithm have a unique solution when there is only a single customer class, and iteration initializations that yield monotonic convergence to this solution are exhibited. It is also proved that the solution is pessimistic relative to the exact queueing network solution.     

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.     

Approximate solution to multichain queueing networks with state dependent service rates

An approximation scheme for solving non-product form queueing networks with multiple chains and state dependent service rates is described. Estimates of the steady state probability distribution are obtained using less computational requirements than the standard solution techniques.The approximation scheme is based on a property called chain conditional balance, which leads to a decomposition of the global balance equations into smaller sets of equations. A technique for combining conditional distributions is examined and used to combine the solutions of conditional balance equations into the final estimates. Expressions for the storage and computational requirements of the approximation algorithm are given and an example is provided.An error analysis is described in which the approximation is tested on a large number of randomly generated queueing networks. The experimental results indicate that the approximation yields good estimates of the steady state distribution, as well as several important performance measures of these networks.     

Feedback invariant discipline and insensitivity in closed queueing networks

Motivated by control theory concepts, we investigate a closed queueing network by adding a feedback path to each node. A feedback invariant service discipline is introduced. This approach differs from the conventional queueing theory approach and provides a new criteria and an intuitive explanation for the insensitivity property in a closed queueing network.     

Regularizability of complex switched server queueing networks modelled as hybrid dynamical systems

The paper considers the problem of the qualitative analysis of complex switched server queueing networks. Such networks can be used to model various flexible manufacturing, communications, and computer systems. We introduce the concept of regularizability for such systems and obtain a necessary and sufficient condition for a switched server queueing network to be regularizable.     

On the role of a queueing network model in the design of a complex assembly system

This paper describes the modeling, analysis and re-design of a complex assembly system consisting of many processes (assembly, testing and inspection) and resources (machines and operators) and an advanced material handling system with intricate routing logics. It presents a systematic approach using both analytical and simulation models for the evaluation and modification of the complex assembly system. It demonstrates the application of a queueing network model to quickly generate rough-cut solutions and provide qualitative information for the evaluation of design alternatives. Iteratively, processes and resources that affect the system performance are identified, one at a time, and the system modified accordingly, until a satisfactory performance is obtained. The preliminary analyses using the queueing network model help to identify bottleneck processes, estimate optimal pallets, and determine a more efficient system layout. The use of the analytical model significantly reduces the number of the lengthy simulation runs. A detailed simulation model is subsequently employed for fine-tuning and further improvement. Compared with the original design, significant improvements have been made: a higher throughput, a reduced cycle time with less operators, and lower WIP inventories.     

Algorithms for nonintegral degrees of multiprogramming in closed queuing networks

The average degree of multiprogramming (DMP) in closed queuing networks is usually assumed to be an integer. Computational algorithms (i.e., normalization constant methods, mean value analysis methods) iterate on, and require, integral DMP values. However, in practice, the average measured DMP is rarely integer-valued.In this paper we present algorithms for the computation of performance measures when the DMP is allowed to be any positive real-valued number. The algorithms match the known performance values when the DMP happens to be an integer. In this respect, the algorithms provide a continuous curve through the known integer-valued points. However, the different algorithms give different results at the noninteger-valued points. The different algorithms are based upon integral DMP algorithms. Two algorithms, DNC and αMVA, are presented which are computationally more efficient and not as cumbersome to implement as the obvious interpolation technique. The interpretation and implications of assuming a nonintegral number of customers in a closed queuing network are given.     

The distribution of network states during residence times in product form queueing networks

Product form queueing networks are so named because their equilibrium state probabilities have a simple product form. This simple form has lead to computationally efficient techniques for obtaining solutions of these networks. Recent work on the probability of network states at those instants when a customer completes service at a service center (departure instants) or arrives at a service center (arrival instants) has revealed a similar product form. The arrival instant result provides a simple, intuitive explanation of the Mean Value Analysis solution technique for product form networks with First-Come-First-Served service centers.In this paper we derive the distribution of network states seen by a particular customer while resident at a particular service center. This distribution too has a relatively simple product form. We use this information to explain in an intuitive way the MVA solution technique for a more general class of network, those containing load independent Processor Sharing and last-Come-First-Served-Preemptive-Resume service centers. It is hoped that, just as the intuitive explanation of the response time formula for FCFS centers has led to approximation techniques for non-separable FCFS centers, this new information may provide approximation techniques for non-separable centers with other scheduling disciplines such as preemptive and non-preemptive priority.     

Integrating scheduling and control functions in computer integrated manufacturing using artificial intelligence

Proper integration of scheduling and control in Flexible Manufacturing Systems will make available the required level of decision-making capacity to provide a flexibly-automated, efficient, and quality manufacturing process. To achieve this level of integration, the developments in computer technology and sophisticated techniques of artificial intelligence (AI) should be applied to such FMS functions as scheduling. In this paper, we present an Intelligent Scheduling System for FMS under development that makes use of the integration of two AI technologies. These two AI technologies — Neural Networks and Expert Systems — provide the intelligence that the scheduling function requires in order to generate goodschedules within the restrictions imposed by real-time problems. Because the system has the ability to plan ahead and learn, it has a higher probability of success than conventional approaches. The adaptive behavior that will be achieved contribute to the integration of scheduling and control in FMS.     

A unified view of product-form approximation techniques for general closed queueing networks

Two major approximate techniques have been proposed for the analysis of general closed queueing networks, namely the aggregation method and Marie's method. The idea of the aggregation technique is to replace a subsystem (a subnetwork) by a flow equivalent single-server with load-dependent service rates. The parameters of the equivalent server are obtained by analyzing the subsystem in isolation as a closed system with different populations. The idea of Marie's method is also to replace a subsystem by an equivalent exponential service station with load-dependent service rates. However, in this case, the parameters of the equivalent server are obtained by analyzing the subsystem in isolation under a load-dependent Poisson arrival process. Moreover, in Marie's case, the procedure is iterative.

In this paper we provide a general and unified view of these two methods. The contributions of this paper are the following. We first show that their common principle is to partition the network into a set of subsystems and then to define an equivalent product-form network. To each subsystem is associated a load-dependent exponential station in the equivalent network. We define a set of rules in order to partition any general closed network with various features such as general service time distributions, pupulation constraints, finite buffers, state-dependent routing. We then show that the aggregation method and Marie's method are two ways of obtaining the parameters of the equivalent network associated with a given partition. Finally, we provide a discussion pertaining to the comparison of the two methods with respect to their accuracy and computational complexity.