Roy Johnston on Queues

Nosokinetics

Queue-Theory and Bed Occupancy

Some Queue-theory Experience from the Past

Roy H W Johnston

RHWJ has expanded on the queue-theory approach in the following notes, in which he attempts to clarify the nature of the problem. He regards the foregoing discussion about '100% utilisation' as somewhat simplistic: we are not dealing just with one queue, but a complex of queues, embedded in a multi-channel service system.

Editor's comment: History teaches. Roy's background is in Physics and Mathematics. Here he explains why average values crashed an innovative American Airlines booking system. The essential lesson is that one needs some degree of managed spare capacity in the system, once the environment is stochastic. Will we ever learn?

Background

In 1963 Roy joined the team adapting the American Airlines real-time reservations system for Aer Lingus, the Irish National Airline. The system designers had previously worked on real-time computing with rocket-related (steady) data flows at Cape Canaveral. In 1964 the system collapsed, at about a third of its planned capacity, because the designers had used average values and had not reckoned with the effects of the stochastic environment. Using detailed simulation, IBM eventually found that the build-up of queues at data-access bottlenecks explained the problem. Meanwhile, at Aer Lingus, using queue theory, substantially the same results were achieved earlier with much less effort.

Modelling the Aer Lingus flight booking system.

The model was defined in terms 'transactions', each consisting of a set of 'messages', being demands for various specialist services. The 'transactions' had a variety of different structures, perhaps about 10 or so. The statistics of the resulting 'transaction mix' were known from the commercial environment; some types were frequent, others less frequent. The sequence of the 'transactions' was chosen using a 'Monte Carlo' type action selecting the 'next transaction', and their arrival-times were Poissonian, i.e. at a defined average rate.

The 'Total Service Time' for each 'transaction' is the 'Service Time' for each of its required service 'messages' plus the 'Time Spent Queuing' for each message to be serviced. The system was complicated by the fact that messages associated with each transaction had to access the mass storage system via a shared communications channel; thus the service time for each message included the queue+service time for the use of the channel, in competition with other messages. Once through the channel, the access-time distribution for the chunk of mass-storage information was rectangular. So the overall service-time distribution was somewhat complex, and esoteric Q-theoretic models had to be invoked, but were available and worked. I seem to remember a Pollacek-Khinchine model being used, which I was able to identify in a book by Saaty. (This probably by now is obsolete and dated.)

The number of transactions currently in the system was highly dependent on the qualitative nature of the current transaction-mix: messages associated with 'heavy' transactions slowed down the processing of other messages, built up the numbers being currently being processed, and expanded the queues. Thus the real-time booking system was a highly unstable non-linear process.

One could however say that at a given mean transaction arrival rate A, and with a given qualitative transaction mix, the mean time in the system would be T and the mean number of transactions in the system would be N, and one could estimate their distributions. The relation between T and A is highly non-linear, and one had to plan the capacity to keep the system in a situation some way from the situation where T starts to rise rapidly. In the end they had to multiplex the communications channel substantially.

I should try to explain how the 'analytical queue simulation model' actually worked. The number of transactions currently 'being processed in' the system may be taken as the product of the mean transaction arrival rate and the mean transaction time. The latter was a function of the lengths of the queues for the specialist services being experienced by the current 'message mix' in the system, these being the messages generated by the transactions currently 'in the system'.

For each new transaction brought into the system, by Monte Carlo choice from the known environmental statistics of transaction types, the oldest transaction currently in the system was thrown out; the old messages were removed and the new ones were added into the 'message mix', and the queue-times for the various services were re-computed. A new mean transaction time emerged, giving a new theoretical 'number of transactions in the system'.

If the new transaction was 'heavy', the resulting increased 'message mix' caused a longer transaction time, implying a need to bring in the next transaction without removing the oldest one. If it was 'lightweight', then another old transaction was thrown out, and the queues were again calculated.

This process generated a distribution of the 'number of transactions in the system' appropriate to the assumed Poissonian arrival rate of various transactions of known relative frequency. One could play with the arrival rate, and get a feel for how this distribution depended on it, in the given complex of queue situations. The extreme non-linearity of the dependence became obvious and understandable.

Compared to detailed simulation, the results were of the status of a 'dirty approximation', but they did enable one to get a rapid feel for where the key bottleneck was. This was confirmed when the detailed simulation work was completed.

Relevance to hospitals.

Hospital systems are somewhat similar, but much more complex. Using the foregoing nomenclature, there are two distinct populations of 'transactions', emergency and planned. Both are stochastic, but neither is clearly Poissonian. Each has a mix of 'messages': sequences of demands for specialised services, and the 'message mix' distributions differ; they should, however, be measurable. The service times are also measurably distributed; some may be quasi-exponential.

The number of available beds is the analogue of the fast-access memory in the computer model, in which the transactions and associated queueing messages were stored between specialist data-accesses. The analogy however is not exact, for bed-occupancy is itself a service, so a 'recovery time' distribution must also be taken into account.

Occupancy time

A typical bed-occupancy time will therefore consist of a combination of recovery time(s) and queue+service time(s) arising from a mix of service requirements. If there is a bottleneck in a particular specialist service domain, this will lead to extended bed-occupancy time, the distributions will become long-tailed, and the bed-queue on trolleys will expand.

The systematic application of queue-theory to this situation suggests itself as an approach enabling key bottlenecks to be identified, and the requisite levels of spare capacity to be identified, such as to avoid the excessive development of queues, taking into account the details of the differing statistics of the stochastic environments in the two distinct client populations.

The maths of this is challenging, and I am not going to attempt it, but if anyone does, I would be interested in being a friendly critical and marginally participating onlooker. I am not proposing it as a sure-fire approach, but perhaps it is worth a look.

[To Contents Page] [To Archive Overview]

Some navigational notes:

A highlighted number may bring up a footnote or a reference. A highlighted word hotlinks to another document (chapter, appendix, table of contents, whatever). In general, if you click on the 'Back' button it will bring to to the point of departure in the document from which you came.