CONTENTS

Dedication

Preface

Acknowledgments

CHAPTER 1: INTRODUCTION

1.1 DESCRIPTION OF THE QUEUEING PROBLEM

1.2 CHARACTERISTICS OF QUEUEING PROCESSES

1.3 NOTATION

1.4 MEASURING SYSTEM PERFORMANCE

1.5 SOME GENERAL RESULTS

1.6 SIMPLE DATA BOOK KEEPING FOR QUEUES

1.7 POISSON PROCESS AND THE EXPONENTIAL DISTRIBUTION

1.8 MARKOVIAN PROPERTY OF THE EXPONENTIAL DISTRIBUTION

1.9 STOCHASTIC PROCESSES AND MARKOV CHAINS

1.10 INTRODUCTION TO THE QTSPLUS SOFTWARE

PROBLEMS

CHAPTER 2: SIMPLE MARKOVIAN QUEUEING MODELS

2.1 BIRTH-DEATH PROCESSES

2.2 SINGLE-SERVER QUEUES (M/M/1)

2.3 MULTISERVER QUEUES (M/M/C)

2.4 CHOOSING THE NUMBER OF SERVERS

2.5 QUEUES WITH TRUNCATION (M/M/C/K)

2.6 ERLANG’S LOSS FORMULA (M/M/C/C)

2.7 QUEUES WITH UNLIMITED SERVICE (M/M/∞)

2.8 FINITE-SOURCE QUEUES

2.9 STATE-DEPENDENT SERVICE

2.10 QUEUES WITH IMPATIENCE

2.11 TRANSIENT BEHAVIOR

2.12 BUSY-PERIOD ANALYSIS

PROBLEMS

CHAPTER 3: ADVANCED MARKOVIAN QUEUEING MODELS

3.1 BULK INPUT (M^[X]/M/L)

3.2 BULK SERVICE (M/M^[Y]/1)

3.3 ERLANGIAN MODELS

3.4 PRIORITY QUEUE DISCIPLINES

3.5 RETRIAL QUEUES

PROBLEMS

CHAPTER 4: NETWORKS, SERIES, AND CYCLIC QUEUES

4.1 SERIES QUEUES

4.2 OPEN JACKSON NETWORKS

4.3 CLOSED JACKSON NETWORKS

4.4 CYCLIC QUEUES

4.5 EXTENSIONS OF JACKSON NETWORKS

4.6 NON-JACKSON NETWORKS

PROBLEMS

CHAPTER 5: GENERAL ARRIVAL OR SERVICE PATTERNS

5.1 GENERAL SERVICE, SINGLE SERVER (M/G/L)

5.2 GENERAL SERVICE, MULTISERVER (M/G/C/·, M/G/∞)

5.3 GENERAL INPUT (G/M/L, G/M/C)

PROBLEMS

CHAPTER 6: GENERAL MODELS AND THEORETICAL TOPICS

6.1 G/E_K/1, G^[K]/M/1, AND G/PH_K/1

6.2 GENERAL INPUT, GENERAL SERVICE (G/G/1)

6.3 POISSON INPUT, CONSTANT SERVICE, MULTISERVER (M/D/C)

6.4 SEMI-MARKOV AND MARKOV RENEWAL PROCESSES IN QUEUEING

6.5 OTHER QUEUE DISCIPLINES

6.6 DESIGN AND CONTROL OF QUEUES

6.7 STATISTICAL INFERENCE IN QUEUEING

PROBLEMS

CHAPTER 7: BOUNDS AND APPROXIMATIONS

7.1 BOUNDS

7.2 APPROXIMATIONS

7.3 NETWORK APPROXIMATIONS

PROBLEMS

CHAPTER 8: NUMERICAL TECHNIQUES AND SIMULATION

8.1 NUMERICAL TECHNIQUES

8.2 NUMERICAL INVERSION OF TRANSFORMS

8.3 DISCRETE-EVENT STOCHASTIC SIMULATION

PROBLEMS

REFERENCES

APPENDIX A: SYMBOLS AND ABBREVIATIONS

APPENDIX B: TABLES

APPENDIX C: TRANSFORMS AND GENERATING FUNCTIONS

C.1 LAPLACE TRANSFORMS

C.2 GENERATING FUNCTIONS

APPENDIX D: DIFFERENTIAL AND DIFFERENCE EQUATIONS

D.1 ORDINARY DIFFERENTIAL EQUATIONS

D.2 DIFFERENCE EQUATIONS

APPENDIX E: QTSPIUS SOFTWARE

E.1 INSTRUCTIONS FOR DOWNLOADING

Index

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.8′2—dc22
2008003734

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 society’s 39th president. Carl’s 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:

http://mason.gmu.edu/jshortle/fqt4th.xhtml.

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.