Processes in the decomposition of network of queues
There are two possible approaches to the problem of a network of service facilities, where an individual customer passes through the network, queueing for service at some or all of these facilities. Either we produce methods by which the network may be decomposed into small manageable parts, or we must attempt to solve simultaneously for all the properties of the network, at a particular time. At present, the class of networks for which comprehensive solutions are known is so restricted that it is usually essential to consider the first approach, at least in the first instance. First we consider the problem of decomposition points, the points at which a stream of customers is broken up into several substreams, heading for different destinations. Conditions are established for a class of decomposition switches, which ensure that if the input stream to the switch is a Markov renewal process, then so are each of the substreams. We then investigate the behaviour of one of these substreams at a subsequent service facility. When the service times are exponentially distributed, an analysis of this, the SM/M/1 queue, based on the properties of the busy cycle, considerably simplifies and extends the results known for it. Some attempt is made to relax the condition on the service time distribution. Since there is always the possibility that a Poisson process approximation to the arrival stream may be acceptable, the dual of this queue, where the sequence of service times forms a Markov renewal process, is considered. This seems a particularly appropriate generalisation, since it allows for different classes of service requirements, perhaps reflecting the origin of customers from various parts of the network. In addition, some results are presented for a queue in which both the arrival times and service requirements depend on the sequence of customer types. Since the output from a queue in a network will form part or all of the input to a subsequent queue, we consider, finally, the departure processes from queues of the types that have been mentioned. Although, in general, it is not possible to describe the departure stream from queues of these types in terms of a particular stochastic process, we can find the distributions of some of the parameters of a very general departure process, in particular, the number of departures from the last queue mentioned above.