Thompson - Fundamentals of Queueing Theory

Copyright 2008 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.
Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic format. For information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data

Gross, Donald.
Fundamentals of queueing theory/Donald Gross, John F. Shortle, Carl M. Harris. 4th ed.
p. cm.
Includes bibliographical references and index.
ISBN 978-0-471-79127-0 (cloth)
1. Queuing theory. I. Shortle, John F., 1969- II. Harris, Carl M., 1940- III. Title. T57.9.G76 2008
519.82dc22
2008003734

Carl Harris, 19402000

This book is dedicated to the memory of Carl M. Harris. Carl and I first entertained the idea of a queueing text back in 1968 and collaborated on the first three editions. We were friends and colleagues from that time until his untimely death from a heart attack while exercising at a local gym, one month after his 60th birthday.

Carl was the BDM International Professor of Operations Research and the founding chair of the Systems Engineering and Operations Research Department for the Volgenau School of Information Technology and Engineering at George Mason University, Fairfax, Virginia. In 1999, he was awarded the Institute for Operations Research and the Management Sciences (INFORMS) Kimball Medal in recognition of distinguished service to the Operations Research profession and the Operations Research Society of America (INFORMS predecessor). He was the societys 39th president. Carls research interests were in the areas of applied probability and statistics, particularly queueing theory and stochastic processes. He authored or co-authored about 80 scholarly papers (on many of which I was fortunate enough to have worked with him.) In addition to the first 3 editions of this book, he co-authored with Saul I. Gass, The Encyclopedia of Operations Research and Management Science.

His warmth, collegiality, and friendship are sorely missed.

Donald Gross

PREFACE

The changes in this fourth edition reflect the feedback from numerous students, teachers, and colleagues since the third edition came out ten years ago. Almost all the material from the third edition is kept in the fourth, however, with a fair amount of editing and reorganization.

Chapter 2 contains a new section on choosing the number of servers and a new subsection on computational issues of the Erlang B formula. The chapter now begins with a section on birth-death processes, which was the old Section 1.10 from the previous edition. Chapter 3 is substantially edited and contains a new section on retrial queues. Chapter 5 contains an expanded discussion of the level crossing method developed by Percy Brill. Chapter 7 is now split into two separate chapters: Chapter 7, Bounds and Approximations, and Chapter 8, Numerical Techniques and Simulation. Chapter 7 includes a new section on network approximations, and Chapter 8 includes a new section on numerical inversion of transforms.

Two appendices are added back to this edition, one on transforms and generating functions and the other on differential and difference equations (by popular request). The appendix on the QtsPlus software is completely rewritten to reflect the changes and expansion made to the software. Also, a subsection on how to use the software is added to Chapter 1. Finally, many more examples and problems are added. In this edition we do not denote which problems are solvable on the computer we leave that up to the discretion of the student and/or instructor. We also do not include here a table on suggested text material for various course lengths (quarter, semester, etc.). Again, we believe that the instructor is the best one to decide.

For errata, updates, and other information about the text and associated QtsPlus software, see the text website:

Donald Gross
John F. Shortle
James M. Thompson

Fairfax, Virginia
March 2008

ACKNOWLEDGMENTS

We are grateful for the assistance given to us over the years by many professional colleagues and students, whose numerous comments and suggestions have been so helpful in improving our work. We particularly thank Prof. Andrew Ross, Eastern Michigan University, Prof. Percy Brill, University of Windsor, and Prof. John Mullen, New Mexico State University, for their very detailed comments, many of which are reflected in this edition. We also appreciate the help and encouragement of our research colleagues, Dr. Martin Fischer and Dr. Denise Masi of Noblis (formerly Mitretek Systems) and Prof. Brian Mark of George Mason University.

With heartfelt thanks, we extend special appreciation once more to our families for their unlimited and continuing encouragement and to all the people at John Wiley & Sons who have been wonderfully supportive of us through these four editions. We also appreciate the support of the Volgenau School of Information Technology and Engineering and the Department of Systems Engineering and Operations Research at George Mason University.

D. G.
J. F. S.
J. M. T.

CHAPTER 1

INTRODUCTION

All of us have experienced the annoyance of having to wait in line. Unfortunately, this phenomenon continues to be common in congested, urbanized, high-tech societies. We wait in line in our cars in traffic jams or at toll booths; we wait on hold for an operator to pick up our telephone calls; we wait in line at supermarkets to check out; we wait in line at fast-food restaurants; and we wait in line at banks and post offices. We, as customers, do not generally like these waits, and the managers of the establishments at which we wait also do not like us to wait, since it may cost them business. Why then is there waiting?