On a Linear Programming Technique for the Steady-State Behavior of Some Queuing Systems

We consider the class of stationary queuing processes whose behavior can be described by a system of difference equations that are linear in the probabilities of the states. We describe a linear programming technique that will provide bounds of any prescribed degree of accuracy for any steady-state quantity expressible linearly in terms of the probabilities. For some queues a standard technique such as the use of generating functions may require a lengthy analysis and may not provide a check on the results. In contrast, the proposed technique is always easy to implement on a computer and, in a certain sense, is self-checking. Illustrative examples are given. The technique is implemented through an algorithm that, as shown by the examples, may give useful results after only a few iterations. We prove that the probability of zero delay for the M / D /2 queue is larger than that for an M / M /2 queue with the same traffic intensity. For a large class of parameter values of the multi-server mixed queue we obtain, with very little computing time, sharp bounds for the average queue size.