Operations Research Models and Methods / Computation

Queueing Add-in

Non-Markovian Queueing Networks


Serial Network - Computer Center Revisited

We again consider the computer network with 10 jobs a minute passing through input processor, central processor and printer, but this time we use the serial network with non-Markovian stations. The results are shown below in which we have incorporated two types of changes. First we have reduced the COV of interarrival times to 0. This means that arrivals occur every 0.1 minutes with no variation. Second, we have reduced the COV of all service times by 0.5. This means that the mean service time is twice the standard deviation.

We analyze each station independently using the non-Markovian approximations for the queueing parameters. We use a second approximation to compute the COV of the departure times of a station. This is important for a serial network because the output of one station becomes the input to the next. Notice that the COV of arrival times are in row 6 of the display and are colored yellow. The first station receives its arrival COV from the data in cell Q6, a user input. Thereafter the arrival COV of a station is the departure COV of the previous one. The stations of the serial system all have the same arrival rate and the COV's of the arrivals and departures are also related. Notice that although the items being processed have no variability at the start, but variability increases as the items pass down the network.

Comparing these results against those obtained with the Poisson assumption for all arrivals and service processes, the queue times are much reduced. We should recall that all these results are approximate and the accuracy of the approximation varies from case-to-case. Perhaps more accurate values can only be obtained with simulation, but these results will have inaccuracies due to statistical variations.


General Network - Job Shop Revisited

We consider again the job shop considered earlier when all arrival and service processes were Poisson. In this case we specify the stations as non-Markovian and use the non-Markovian queueing formulas. The only difference between this case and the one considered earlier has the coefficients of service times reduced to 0.5.

A difficulty arises when considering this kind of system. The arrivals to each station may come from several other stations. Although we compute the departure COV for each station, there is no simple way to compute the COV of an arrival process consisting of several streams coming from different stations. Notice that the program does not compute the interarrival COV's in row 39 as it did for the serial case.

Although we don't have a general approximation for a complete analysis for this situation, this option may be useful in several ways. By leaving all the COV's of arrival times as 1, the analysis yields something of an upper bound for the queues of the network. With the arrival COV at 1, the arrivals appear to be random at a station. Although it is conceivable that a situation might occur that results in a COV greater than 1, we suspect that this would not be likely. Putting the arrival COV's at 0, should provide lower bound estimates of the queue statistics. Thus the two extremes should provide upper and lower bound analyses of the times and numbers for a system.

Another use for this structure is to set all variation (all COV's) to zero. Many networks have complex flows between stations. Simply solving for the arrival rates at each station is not trivial. The equations provided by the add-in accomplish this result with no additional effort.


Queue Simulation

Operations Research Models and Methods
by Paul A. Jensen and Jon Bard, University of Texas, Copyright by the Authors