A. Y. Khinchin - Mathematical Methods in the Theory of Queuing

MATHEMATICAL

METHODS

IN THE

THEORY OF QUEUING

MATHEMATICAL

METHODS

IN THE

THEORY OF QUEUING

A. Y. KHINCHIN

Translated by D. M. Andrews
and M. H. Quenouille

Dover Publications, Inc.

Mineola, New York

Bibliographical Note

This Dover edition, first published in 2013, is an unabridged republication of the work originally published by Charles Griffin & Company, Ltd., London, and Hafner Publishing Company, New York, in 1960. The Dover edition uses the standardized spelling of the authors name, Khinchin. It was originally printed as Khintchine.

International Standard Book Number

ISBN-13: 978-0-486-49096-0

ISBN-10: 0-486-49096-3

Manufactured in the United States by Courier Corporation

49096301

www.doverpublications.com

In the realm of practical human affairs, situations frequently arise in which there is a demand for service in the face of which the serving organisation, since it provides only a limited number of serving units, is unable to satisfy all incoming demands. We all know examples of such situations. Queues in shops or at ticket offices, in refreshment bars, at hairdressers, etc.; the impossibility of getting a ticket for a train that one wishes to travel on, owing to its being booked up; the delay in landing an aircraft caused by the lack of free runways; the delay in repairing a machine which has broken down, on account of the lack of repair gangs all these and many other examples like them are, apart from the substantial divergence of their actual content, very similar to one another from the point of view of form. In all such instances our theory has one main task to establish as clearly as possible the interdependence of the number of serving units and the quality of the service. As regards this, the quality of the service in different instances is, naturally, measured by different indices. Usually, either the percentage of demands which are turned down (the percentage of passengers that did not get a ticket for a given train) or the average time of waiting for the commencement of the service (queues of different kinds) is taken as the index. Obviously, to achieve a higher quality of service requires in all cases a greater number of service units. However, it is evident that an excessive number will result in a superfluous outlay of effort and material resources. Thus, in practice, the problem is usually resolved by the quality of the service initially finding its necessary level, and thereafter by discovering the minimal number of service units by which this level can be attained.

In problems of a similar kind it is nearly always necessary to take into account the influence of the element of chance upon the course of the phenomenon under consideration. The quantity of incoming demands is not as a rule constant, but undergoes occasional fluctuation. The time of serving the demands is not in the majority of problems a standard one, but is subject to fluctuation from one problem to another. All these chance elements do not by any means have the character of little disturbances, breaking up the even and regular course of the phenomenon; on the contrary they form the main feature in our picture of the processes to be studied. Thus it is natural that the concepts and methods of the theory of probability a mathematical discipline devoted to the study of the frequencies of events should become a mathematical instrument of the theory of queueing.

The aim of the present work is to acquaint the reader with the main ideas, methods, and different ways of thought which govern the application of the theory of probability to questions of mass service. The need for a monograph of this kind has long been felt both by mathematicians and by practical workers (in the first instance by those who, in their own time, brought the theory under consideration into being and have remained up till now its chief users). This need is so much the more reinforced by the fact that few available explanations of the general theory exist, even outside Russia.

In itself, of course, the present monograph cannot in any way pretend to present all the information there is to be communicated. The theory of queueing has developed considerably in recent times, and for only a fractional explanation, or even to put down the most important of its achievements, a large volume would be required. However, I have set myself no such task. My object has been to throw some light on the main character of the most important examples, i.e. on the method of employing probability arguments in questions of mass service, and from this methodological statement of aims I have drawn the choice of material for my monograph. Special attention has been paid to the chief exponent of the theory, A. K. Erlang, whose investigations are not by any means known to the degree they deserve. I have also incorporated into the book a significant number of the ideas of K. Palm, who is doing most at present to carry on Erlangs work. To a certain extent I have also joined in the attempt one which continues in our own time to find simpler methods of investigation in contrast with the analytical methods which have been in favour almost without a break from the time of Erlangs classic work, and which required the establishment of differential, partial-differential, and integral equations. As far as this is concerned I would draw the readers attention to . An attempt to form a general elementary theory was undertaken a short while ago in an interesting article by Lundkvist (Ericsson Technics, 1953).

The preparation of this monograph was greatly hampered by the fact that all the fundamental literature comes from the pens of workers in the practical field, and is therefore unsatisfactory from a mathematical point of view. To give each explanation a form that was mathematically acceptable I was not able to leave a single discussion in its original state; it was necessary either substantially to supplement the authors reasoning or to reject it altogether and substitute a different argument. Similarly, where new concepts were being introduced it was necessary in many cases to define them differently, since the definitions given by the authors seemed insufficiently precise.

In order to help the reader to link the general concepts with concrete phenomena, I use terminology borrowed from telephonic practice during the course of the whole book hitherto questions in this field have constituted the greatest stimulus to the development of the theory of mass service. Thus I speak of calls (instead of demands or requirements), of losses (instead of refusals), of the length of a conversation (instead of a service) etc. However, in all instances everything that is said can be naturally related to any kind of mass service, by making the necessary changes in terminology.

The book is divided into three parts of which the first, the largest, is devoted to the study of the stream of incoming calls and contains no questions of service at all (the other two parts being devoted to this). It seemed appropriate to confine the study of the incoming stream to a particular part of the book, not only because, in order to provide a good service, it is necessary to know what you are serving, but also because the theory of an incoming stream of calls is none other than the general theory of the random sequence of uniform occurrences, finding a broad circle of applications even in fields unconnected with any kind of service (for example, in questions of the radioactive disintegration of atoms).

I have tried to make the book accessible to anyone who has mastered the main concepts of the theory of probability and followed some course, however short, in mathematical analysis. In many instances the explanation could have been abbreviated if, instead of introducing the full proof of this or that assertion, I had allowed myself to appeal to the results of an appropriate theory of probability (Markoff chains, random processes, ergodic theories). However, wishing to produce a book accessible to as wide as possible a circle of readers, I have hardly ever yielded to such a temptation.