Analytic and External Control Variates for Queueing Network Simulation

While external control variates (ECVs) have long been advocated for reducing the variance of simulation estimators, the lack of tractable external control systems and the almost doubling of the computational burden has hindered their use. This paper presents preliminary work on a new type of control variate, the analytic control variate (ACV), that has the advantages of the ECV but requires much less additional computation. Use of an ACV is demonstrated for open queueing networks.     

Rare-Event Simulation of Non-Markovian Queueing Networks Using a State-Dependent Change of Measure Determined Using Cross-Entropy

A method is described for the efficient estimation of small overflow probabilities in nonMarkovian queueing network models. The method uses importance sampling with a state-dependent change of measure, which is determined adaptively using the cross-entropy method, thus avoiding the need for a detailed mathematical analysis. Experiments show that the use of rescheduling is needed in order to get a significant simulation speedup, and that the method can be used to estimate overflow probabilities in a two-node tandem queue network model for which simulation using a state-independent change of measure does not work well.     

Using Cumulant Functions in Queueing Theory

A new approach for obtaining the transient solution for the first and second moments of the system size in a finite capacity M/M/1 queueing systems is developed. The approach uses the cumulant generating function which has previously been used in the analysis of compartmental models but has not been used to analyze queueing systems.     

A Closed Queueing Maintenance Network with Two Repair Centres

In this paper we introduce a model to determine the maintenance float needed to maximize the availability of an operating system with N number of circulating units. An implicit enumeration algorithm is used as a solution technique to the closed queueing maintenance network with two types of repairs: minor and major repairs. It is shown that when there is no differentiation of repair type, this special case is obtained as a by-product of the two-repair-centre model. This paper assumes exponential failure times and exponential repair times with load-independent servers. The approach followed in this paper provides an approximate and simple way to solve the maintenance-float problem of this complex closed-network system.     

Operational Analysis of Nodal Hierarchies in Network Systems

The general location-allocation problem is identified and discussed. The hierarchical extension of this problem is then shown to be of especial interest. A computational algorithm for heuristic solution of the hierarchical problem is described. This algorithm appears to yield solutions of high quality. Finally a numerical problem is examined.     

Queueing with Cyclic Arrival Distributions and Variable Service Facilities: A Simulation Approach

This paper develops a near optimal policy for opening a second counter in a quick-service restaurant when n persons are in the first line, given that the arrival process is cyclic rather than purely stationary. A simulation was written in GPSS which permitted the use of different arrival generators during different time segments of the simulated day. Results indicate that as n is varied, waiting time and utilization levels exhibit an S-shaped curve between the pure 1 facility and the 2 facility cases. Results also indicate that a cyclic arrival process greatly increases (relative to the case of exponential arrivals) mean waiting time, facility utilization, and the range of n. Finding the optimal (least cost) value of n is illustrated for cases in which costs of customer waiting time can be meaningfully imputed.     

A Multiclass Feedback Queueing Network with a Regular Skorokhod Problem

We consider a four-class two-station network with feedback, with fluid inputs and a head-of-the-line generalized processor sharing discipline at each station. We derive the Skorokhod Problem associated with the network and obtain algebraic sufficient conditions for Lipschitz continuity of the associated Skorokhod Map. This provides the first example of a multiclass network with feedback for which the associated Skorokhod Problem has been proved to be regular. As an elementary application, we show that under the conditions which guarantee Lipschitz continuity the network is stable if and only if the usual load conditions apply.     

Some Applications of Queueing Theory in Operational Research (1953-89)

An account of the development of queueing theory from an operationalresearch perspective is given. The theory discussed ranges fromthe simple queue, finite queues, and queues in tandem, to non-Poissoninput and service-queueing systems. A methodology for analysingthe systems is outlined, and appropriate references given. Allthese developments relate to models used in investigating realproblems undertaken by different operational research departments.     

Digital Simulation in Operational Research

Journal of the Operational Research Society -     

Operational Research in a Developing Country: The Example of Jordan

Much interest has been expressed in recent years in the problem of applying operational research in less developed countries. This paper examines the problems and possibilities of developing an interest in operational research in one such country, the Hashemite Kingdom of Jordan.     

Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm

We study a model of controlled queueing network, which operates and makes control decisions in discrete time. An underlying random network mode determines the set of available controls in each time slot. Each control decision “produces” a certain vector of “commodities”; it also has associated “traditional” queueing control effect, i.e., it determines traffic (customer) arrival rates, service rates at the nodes, and random routing of processed customers among the nodes. The problem is to find a dynamic control strategy which maximizes a concave utility function H(X), where X is the average value of commodity vector, subject to the constraint that network queues remain stable.We introduce a dynamic control algorithm, which we call Greedy Primal-Dual (GPD) algorithm, and prove its asymptotic optimality. We show that our network model and GPD algorithm accommodate a wide range of applications. As one example, we consider the problem of congestion control of networks where both traffic sources and network processing nodes may be randomly time-varying and interdependent. We also discuss a variety of resource allocation problems in wireless networks, which in particular involve average power consumption constraints and/or optimization, as well as traffic rate constraints.     

马尔可夫排队模型中的合作问题分析

结合合作博弈理论,建立了合作条件下的马尔可夫排队模型.模型以多个提供同质服务的M/M/1马尔可夫排队系统达成协议形成联盟,共用一台服务器为顾客服务为研究重点,以机构维护服务器的成本与顾客在系统中排队等待的时间成本之和作为成本函数,得出形成联盟共用服务器可以降低总成本.最后给出总成本在形成联盟的机构中的分配规则.     

Analysis of Open Discrete Time Queueing Networks: A Refined Decomposition Approach

This paper deals with approximate analysis methods for open queueing networks. External and internal flows from and to the nodes are characterized by renewal processes with discrete time distributions of their interarrival times. Stationary distributions of the waiting time, the queue size and the interdeparture times are obtained using efficient discrete time algorithms for single server (GI/G/1) and multi-server (GI/D/c) nodes with deterministic service. The network analysis is extended to semi-Markovian representations of each flow among the nodes, which include parameters of the autocorrelation function.     

Taking Account of Correlations Between Streams in Queueing Network Approximations

In this paper we describe a new variation on QNA, the Queueing Network Analyzer (Whitt [38]). QNA calculates approximate congestion measures for a network of queues. The variant proposed here allows us to relax QNA’s assumption that certain counts of events in the network are uncorrelated. Following QNA, the network is approximated in terms of three basic operations on streams, namely, queueing, splitting and superposition, and random quantities of interest are characterized approximately by two moments. The approach differs from QNA in that instead of expressing the network operations as transformations applied to two-moment characterizations of the inputs, it expresses these operations as regression relations between counts in the output streams and the input streams. In essence, we substitute approximate regression relationships between random variables for QNA’s approximate moment relationships. This device allows us to enhance QNA’s moment relationships with information about correlations between the streams. We compare the performance of the proposed approach with QNA on a simple feed-forward network to demonstrate the need for taking account of correlation. We also discuss some of the limitations of this approach, particularly its difficulty in handling feedback, and give some ideas to improve accuracy.AMS subject classification: 60K25, 68M20, 90B22Colm O’Cinneide has left Purdue University after 10 wonderful years of research and teaching, and now works for Deutsche Asset Management in New York. This research has been supported in part under NSF grant DMI-9713730.This revised version was published online in June 2005 with corrected coverdate     

生产流水线中的排队问题

本文讨论产品以Poisson过程到达,有K道加工工序,每加工点是有限容量且服务服从指数分布带受阻的排队网络,并给出了平稳条件和在平稳条件下以三节点组合逼近方法得到平均队长．     

Variability Analysis for a Two-station Queueing Network in Heavy Traffic with Arrival Processes Driven by Queues

The law of the iterated logarithm(LIL) for the performance measures of a two-station queueing network with arrivals modulated by independent queues is developed by a strong approximation method. For convenience, two arrival processes modulated by queues comprise the external system, all others are belong to the internal system. It is well known that the exogenous arrival has a great influence on the asymptotic variability of performance measures in queues. For the considered queueing network in ...     

A Materialist Analysis of Operational Research

Accounts of the development and practice of operational research have commonly stressed its timeless universality as a method for rational decision-making. In this paper operational research is seen as one element in the managerial response to problems of complexity and uncertainty within an economic system characterised by institutionalised conflict. Both the material and ideological functions of ‘management science’ in private and public enterprise are analysed, and characteristics are identified of an emergent ‘workers science’. Editor's Note The title of this paper contrasts the materialistic approach with the idealistic approach, and the content of the paper disowns the latter. Evidently there are alternative but overtly political terms for both adjectives.It would be stupid if O.R. were to ignore the political facts of life which play so great a part in the decisions and policies with which O.R. is concerned. But, as the authors acknowledge, other interpretations of history than those presented here are at least possible.Contributions offering alternative schemata, or based on other paradigms, are invited and will be given careful consideration.