MARKOV NETWORK PROCESSES WITH STRING TRANSITIONS

This study introduces a Markov network process called a string-net. It s state is the vector of quantities of customers or units that move am ong the nodes, and a transition of the network consists of a string of instantaneous Vector increments in the state. The rate of such a stri ng transition is a product of a transition-initiation rate and a strin g-generation rate. The main result characterizes the stationary distri bution of a string-net. Key parameters in this distribution satisfy ce rtain ''polynomial traffic equations'' involving the string-generation rates. We identify sufficient conditions for the existence of a solut ion of the polynomial equations, and we relate these equations to a pa rtial balance property and throughputs of the network. Other results d escribe the stationary behavior of a large class of string-nets in whi ch the vectors in the strings are unit vectors and a string-generation rate is a product of Markov routing probabilities. This class include s recently studied open networks with Jackson-type transitions augment ed by transitions in which a signal (or negative customer) deletes uni ts at nodes in one or two stages. The family of string-nets contains e ssentially all Markov queueing network processes, aside from reversibl e networks, that have known formulas for their stationary distribution s. We discuss old and new variations of Jackson networks with batch se rvices, concurrent or multiple-unit movements of units, state-dependen t routings and multiple types of units and routes.