In many applications, rather than passing through a single queue, a calling unit will pass though a series of queues. An example is the registration procedure at a college where students visit a number of stations as required for the approval of their academic program. Each station involves one or more servers and a queue of waiting students. Another example is a job shop where machines are grouped by function. A collection of machines of the same type can be modeled as a queuing station. A job entering the shop is processed at one or more stations before it leaves. The analysis of these types of networks can be quite difficult unless they have some special structure.

Analytical results are available when all external arrivals to the network are Poisson, each queue within the network has unlimited capacity and exponential service times, and transfers from one queue to another are made randomly according to given probabilities. This type of system is called a Jackson network, and some of its steady-state behavior can be described using the same formulas developed for single station Markovian queues. As we have seen, these formulas are very easy to apply and yield numerical results that are critical to the design of a system.

When the individual queuing stations are not Markovian the results are approximate.

Example: Computer Center

This example illustrates a serial queuing network where the external input enters the first station and the remaining stations process the entire amount. The Queuing add-in constructs the arrays shown below to model the network with three stations. Data is for the example problem. Column B holds titles for the parameters and results of the analysis. In columns C through E in row 2, we have placed the names for the three network devices. Row 3 shows the arrival rates. The yellow color in columns D through E indicates that these cells hold formulas. In fact, they all refer to the entry in cell G2, where the arrival rate to the first station of the network is specified. Row 4 holds the service rates for the devices, which are computed from the mean processing times given in the problem statement. Row 5 holds the number of servers of each device. We have entered the minimum number of servers that can handle the load. Any smaller number results in an unstable system.

The remainder of the rows of the display show the results that are computed with the queuing functions provided by the add-in. The rows in columns C, D, and E describe the results for the individual stations. The station results are added together to obtain the system results in column G. For a network with arrivals and services governed by exponential distributions, each queuing station may be analyzed independently with the formulas derived for Poisson processes.

Reviewing the efficiencies for the three stations reveals that the central processor is the least busy, while the printers are busy 97% of the time. Of the almost 50 jobs in the system, on the average, 43 of them are waiting or in-process at the printers. From the system results we see that on the average a job spends about 5 minutes in the system.

Any number not colored yellow may be changed by the user to obtain new results. For example, one might wonder if increasing the number of printers would result in significantly lower throughput times for jobs. That can be immediately determined by increasing the number in cell E5.

The General Network

To illustrate the general network, we modify the problem slightly by changing the proportions of the jobs passing through each device.

The Queuing add-in provides a General network option for entering the more complex data for this system. The display for this option is shown below with the data entered for the example. The display has been placed with its upper-left corner at cell B16.

For this option, a new data item appears in row 17, the Independent Arrival Rate. Each station may have arrivals from outside the system as indicated by the entries in this row. For the current example, all arrivals occur to the Input processor, so the other entries in this row are 0. The arrival rate in row 18 is a computed quantity and the contents of the row should not be changed. As before, the service rates and number of servers are controlled by the user. The numbers of servers shown here are the smallest numbers that will satisfy the demand at the three stations.

Data concerning the proportions of jobs passing from one station to another is entered in the table in the range C31:E33. We call this the transfer matrix because it shows the proportions of the flow transferred from one station to another. In row 31 we see that 80% of the flow transfers from the Input processor to the central processor. The remaining 20% leaves the network. From row 32 we see that 40% of the flow passing through the central processor goes to the printer.

The arrival rate shown in row 18 is computed with an equation involving the Inverse of the Augmented matrix. The Augmented matrix is the transfer matrix subtracted from the identity matrix The entries in the Transfer matrix are entirely general as long as the Inverse exists. An entry on the diagonal represents a recycling through the station. In many cases the numbers in the matrix represent proportions of flow transferred. A requirement of the Jackson network is that the routing be probabilistic. That is, a particular entity leaving a station will transfer the next with the given probability distribution.