Brownian models of open processing networks: Canonical representation of workload

• 成果类型: Article
• 署名作者: Harrison, JM
• 署名单位: Stanford University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/aoap/1019737665
• 发表日期: 2000
• 页码: 75-103
• 关键词: heavy traffic analysis; scheduling networks; controllable inputs; queuing-networks; closed network; queues

摘要

A recent paper by Harrison and Van Mieghem explained in general mathematical terms how one forms an equivalent workload formulation of a Brownian network model. Denoting by Z(t) the state vector of the original Brownian network, one has a lower dimensional state descriptor W(t) = MZ(t) in the equivalent workload formulation, where M can be chosen as any basis matrix for a particular linear space. This paper considers Brownian models for a very general class of open processing net works, and in that context develops a more extensive interpretation of the equivalent workload formulation, thus extending earlier work by Laws on alternate routing problems. A linear program called the static planning problem is introduced to articulate the notion of heavy traffic for a general open network, and the dual of that linear program is used to define a canonical choice of the basis matrix M. To be specific, roms of the canonical M are alternative basic optimal solutions of the dual linear program. If the network data satisfy a natural monotonicity condition, the canonical matrix M is shown to be nonnegative, and another natural condition is identified which insures that M admits a factorization related to the notion of resource pooling.