The Lecture Notes are intended to report quickly and informally, but on a high level, new developments in mathematical economics and operations research. In addition reports and descriptions of interesting methods for practical application are Particularly desirable. The following items are to be published: 1. Preliminary drafts of original papers and monographs 2. Special lectures on a new field, or a classical field from a new point of view 3. Seminar reports 4. Reports from meetings Out of print manuscripts satisfYing the above characterization may also be considered, if they continue to be in demand. The timeliness of a manuscript is more important than its form, which may be unfinished and prelimi nary. In certain instances, therefore, proofs may only be outlined, or results may be presented which have been or will also be published elsewhere. The publication of the "Lecture Notes" Series is intended as a service, in that a commercial publisher, Springer Verlag, makes house publications of mathematical institutes available to mathematicians on an inter national scale. By advertising them in scientific journals, listing them in catalogs, further by copyrighting and by sending out review copies, an adequate documentation in scientific libraries is made possible. Manuscripts Since manuscripts will be reproduced photomechanically, they must be written in clean typewriting. Hand written formulae are to be filled in with indelible black or red ink. Any corrections should be typed on a separate sheet in the same size and spacing as the manuscript. All corresponding numerals in the text and on the correction sheet should be marked in pencil. Springer-Verlag will then take care of inserting the corrections in their proper places. Should a manuscript or parts thereof have to be retyped, an appro priate indemnification will be paid to the author upon publication of his volume. The authors receive 25 free copies. Manuscripts written in English, German, or French will be received by Prof. Dr. M. Beckmann, Depart ment of Mathematics, Brown University, Providence, Rhode Island 0 29 12/USA, or Prof. Dr. H. P. Ktinzi, Institut fi.ir Operations Research und elektronische Datenverarbeitung der U niversitat Ztirich, Sumatrastra.Be 30, 8006 Ztirich. Die Lecture Notes sollen rasch und inform ell, aber auf hohem Niveau, tiber neue Entwicklungen der mathematischen Okonometrie und Unternehmensforschung berichten, wobei insbesondere auch Berichte und Darstellungen der ftir die praktische Anwendung interessanten Methoden erwtinscht sind. Zur Veroffentlichung kommen: 1. Vorlaufige Fassungen von Originalarbeiten und Monographien. 2. Spezielle Vorlesungen tiber ein neues Gebiet oder ein klassisches Gebiet in neuer Betrachtungsweise. 3. Seminarausarbeitungen. 4. Vortrage von Tagungen. Ferner kommen auch altere vergriffene spezielle Vorlesungen, Seminare und Berichte in Frage, wenn nach ihnen eine anhaltende Nachfrage besteht. Die Beitrage di.irfen im Interesse einer gri:iBeren Aktualitat durchaus den Charakter des Unfertigen und Vorlaufigen haben. Sie brauchen Beweise unter Umstanden nur zu skizzieren und di.irfen auch Ergebnisse enthalten, die in ahnlicher Form schon erschienen sind oder spater erscheinen sollen. Die Herausgabe der ,Lecture Notes" Serie durch den Springer-Verlag stellt eine Dienstleistung an die m athematischen Institute dar, indem der Springer-Verlag ftir ausreichende Lagerhaltung sorgt und einen graBen internationalen Kreis von Interessenten erfassen kann. Durch Anzeigen in Fachzeitschriften, Auf nahme in Kataloge und durch Anmeldung zum Copyright sowie durch die Versendung von Be sprechungsexemplaren wird eine ltickenlose Dokumentation in den wissenschaftlichen Bibliotheken ermi:iglicht. Lecture Notes in Operations Research and Mathematical Economics Edited by M. Beckmann, Providence and H. P. KUnzi, ZUrich 2 U. Narayan Bhat Case Western Reserve University, Cleveland, Ohio A Study of the Queueing Systems M/G/1 and GI/M/1 1968 Springer-Verlag Berlin Heidelberg GmbH ISBN 978-3-662-38801-3 ISBN 978-3-662-39706-0 (eBook) DOI 10.1007/978-3-662-39706-0 All rights reserved. No part of this book may be translated or reproduced in any form without written permission from Springer Verlag. ©Springer-Verlag Berlin Heidelberg 1968. Library of Congress Catalog Card Number 68-19088. Title No. 3752. PREFACE This study has grown out of a part of the author's thesis "Some Simple and Bulk Queueing Systems: A Study of Their Transient Behavior" submitted to the University of Western Australia (1964) and a course on Queueing Theory given to graduate students in the Operations Research Group of Case Institute of Technology, Cleveland, Ohio. The one semester course (approximately 35 hours) consisted of the following topics. (i) Some of the important special queues such as M/M/s, M/D/s, M/Ek/1 etc., with emphasis on the different methods employed in the transient as well as steady state solution. (ii) Imbedded Markov chain analysis of M/G/1 and GI/M/1 as given in the joint paper of the author and N. U. Prabhu as well as the papers of D. G. Kendall. [All notations and papers are referred to later in the notes]. (iii) The contents of this memorandum. The author feels that such a course prepares the students adequately for an advanced course in Queueing Theory involving topics on Waiting Times, the General Queue GI/G/1 and other ramifications such as Priorities, etc. A few words regarding the approach adopted in this study may not be out of place. So far, the time dependent behavior of queueing systems has not found a place in courses given outside the Department of Mathematics. In the mathematical analysis of the systems a wide variety of techniques have been developed and used and some of the most complicated systems have been investigated. However, even though queueing systems are systems of real life situations, improvements in the design of such systems do not match with the increase in theoretical developments. There seems to exist a wide gulf between the theoretical researcher and the one who uses his results. It seems to us that this is due to the methods of analysis used and the form of results obtained. Analytically these methbds are powerful and can be used in very complex situations as demonstrated in the papers mentioned in bibliographies on the subject. However, there is a serious disadvantage in these methods, which an analytically oriented researcher tries to neglect. Plainly speaking, the results, given in terms of transforms, very often with more than one argument, fail to make sense to an applied researcher. In simpler situations means and variances could be deduced without much difficulty from these transforms. But, as the trans forms get complicated, even these operations need extra dexterity in mathematical manipulations. This seems to us, has been the main reason for the gulf that exists between the theoretician and the applied scientist, even though so much ingenuity has been shown in tackling a variety of technical problems on paper by some of the ablest people in the world. As Kendall (1964) has aptly put it "much of the detail of the queue - theoretic scene has been obscured by the Laplacian curtain". As a result, a researcher with not much sophistication in mathematical technqiues, takes the easiest and simplest way out of his complex problems by assuming steady state from the start of the operation and/or saying that all arrival or service time distributions can be approximated by an exponential distribution, without loss of significant information. Over the last few years several researchers have directed their attention in remedying this defect and for the single server systems with (i) Poisson arrivals and general service times and (ii) general independent arrivals and negative exponential service times, a good number of combinatorial approaches have come out. Some of the investigations of Prabhu (1965), Takacs (1967) and the present author belong to this category. Takacs uses generalization and extensions of the classical Ballot theorem to give a combinatorial study of the underlying stochastic process. The present author worked closely with Prabhu and has been able to add much to what has been done by Prabhu and straighten out some of his methods which may seem to be roundabout. The method given by Prabhu is based on the study of the waiting time processes in these systems. It is true that if either one of the waiting time or queue length processes is studied, the other one follows automatically. However, it should also be noted that the queue length process is discrete valued and independent of the queue discipline to a large extent. Because of this property a study based on the queue length process has several advantages. The present author has developed such a method which deals with the queue length process directly and makes minimal use of transforms. The only time we use transforms is while getting some steady state results. Although it is possible to derive such results without resorting to transforms, an appeal to transforms makes it much simpler - and it is our aim to achieve simplicity in methods. With a few exceptions, the results presented in the following pages have appeared elsewhere in journals and books. However, as more and more schools have started teaching Queueing Theory formally, we hope the approach given in this memorandum will be very useful in teaching the time dependent behavior of queueing systems, which seems to be finding its due place in applied research lately. In this work the author has received direct and indirect encouragement from Professor N. U. Prabhu of Cornell University. Grateful acknowledgments go to him. I would be failing in my duty if I do not thank Miss Susanne Preston for her excellent job in typing this manuscript. TABLE OF CONTENTS Page . . PREFACE . i . . . . . . INTRODUCTION 1 1. THE QUEUE M/G/1 WITH GROUP ARRIVALS . 8 1.1 DESCRIPTION AND DEFINITIONS 8 . . . . 1.2 BUSY PERIOD TRANSITIONS 10 1.3 GENERAL TRANSITIONS OF Q(t) 20 . . . . . . . 1.4 LIMITING BEHAVIOR OF Q(t) 25 1.5 Q(t) AND THE UNEXPENDED SERVICE TIME . 31 . . . . 1.6 WAITING TIME W(t): AN APPROACH THROUGH Q(t) 33 . . . . 1.7 WAITING TIME W(t): AN INDEPENDENT STUDY . 35 . . . . 1.8 THE QUEUE M/G/1 WITH BALKING • 39 . . . . 1.9 SPECIAL CASES 41 2. THE QUEUE GI/M/1 WITH GROUP SERVICE . 44 . . . . 2.1 DESCRIPTION AND DEFINITIONS 44 . . . . 2.2 THE BUSY PERIOD T 45 0 . . . . . . . . . . 2.3 THE BUSY PERIOD T. 48 1. . . . . 2.4 THE BUSY CYCLE . 51 2.5 GENERAL TRANSITIONS OF Q( t) 57 . . . . . . . . 2.6 WAITING TIME W(t) 62 . . . . . 3. QUEUEING SYSTEMS IN DISCRETE TIME 63 . . . . 3.1 THE QUEUE Geom/G/1 . 64 3.2 THE QUEUE GI/Geom/1 68 . . . . . . . BIBLIOGRAPHY 72 INTRODUCTION A 'queue' is a waiting line of units demanding service at a service facility (counter); the unit demanding service is called the 'customer' and the device at which or the person by whom it gets served is known as the 'server'. This terminology is used in a wide context. Here are a few realistic examples of this customer - server mechanism. (i) Vehicles demanding service arrive in a garage and depending on the number of employees, one or more vehicles may be repaired at a time. (ii) Patients arrive at a doctor's clinic for treatment. Even if some appointment system exists, due to the emergency service rendered, there is a random element present in the arrival scheme and, there is a possibility of a waiting line building up. (iii) In a telephone exchange, the incoming calls are the customers who demand service in the form of telephone conversations. (iv) Passengers demanding tickets queue up in front of a ticket counter. It is possible to give numerous examples of this type, where a queue situation exists in one form or the other. As suggested by the above problems, some of these situations differ from each other in several details. However, it is not difficult to see that all these situations have certain common basic characteristics.