An Elementary Introduction to Queueing Systems-

An Elementary Introduction to

QUEUEING

SYSTEMS

9190_9789814612005_tp.indd 1 5/5/14 3:20 pm

May 2, 2013 14:6 BC: 8831 - Probability and Statistical Theory PST˙ws

This page intentionally left blank

NEW JERSEY • LONDON • SINGAPORE • BEIJING • SHANGHAI • HONG KONG • TAIPEI • CHENNAI

World Scientific

University of Calgary, Canada

An Elementary Introduction to

QUEUEING

SYSTEMS

Wah Chun Chan

9190_9789814612005_tp.indd 2 5/5/14 3:20 pm

Published by

World Scientific Publishing Co. Pte. Ltd.

5 Toh Tuck Link, Singapore 596224

USA office: 27 Warren Street, Suite 401-402, Hackensack, NJ 07601

UK office: 57 Shelton Street, Covent Garden, London WC2H 9HE

British Library Cataloguing-in-Publication Data

A catalogue record for this book is available from the British Library.

AN ELEMENTARY INTRODUCTION TO QUEUEING SYSTEMS

Copyright © 2014 by World Scientific Publishing Co. Pte. Ltd.

All rights reserved. This book, or parts thereof, may not be reproduced in any form or by any means,

electronic or mechanical, including photocopying, recording or any information storage and retrieval

system now known or to be invented, without written permission from the publisher.

For photocopying of material in this volume, please pay a copying fee through the Copyright Clearance

Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to photocopy

is not required from the publisher.

ISBN 978-981-4612-00-5

Printed in Singapore

v

This book is dedicated to the memory of my uncle and aunt,

Mr. and Mrs. Lap Hoi Chan, who supported me during my youth,

and my professor, Dr. Donald A. George, who inspired me

in the study of the theory of probability.

May 2, 2013 14:6 BC: 8831 - Probability and Statistical Theory PST˙ws

This page intentionally left blank

vii

ACKNOWLEDGEMENTS

The author wishes to thank his wife, Yu-Chih, and his family

members, Eileen and Al, Jean and Aaron, Vivian and Brian, and

An-Wen for their encouragement and support during the

preparation of the book. Also, a special thanks to Eileen for her

skillful typing of the manuscript in her busy work schedule.

May 2, 2013 14:6 BC: 8831 - Probability and Statistical Theory PST˙ws

This page intentionally left blank

ix

CONTENTS

Preface

Chapter 1

Modeling of Queueing Systems .............................................................. 1

1.1 Mathematical Modeling ........................................................................ 1

1.2 The Poisson Input Process .................................................................. 3

1.3 Superposition of Independent Poisson Processes .................... 8

1.4 Decomposition of a Poisson Process ............................................ 10

1.5 The Exponential Interarrival Time Distribution ..................... 12

1.6 The Markov Property or Memoryless Property ...................... 13

1.7 Relationship Between the Poisson Distribution and the

Exponential Distribution ................................................................... 14

1.8 The Service Time Distribution ........................................................ 15

1.9 The Residual Service Time Distribution ..................................... 17

1.10 The Birth and Death Process ........................................................... 19

1.11 The Outside Observer’s Distribution and the Arriving

Customer’s Distribution .................................................................... 25

Chapter 2

Queueing Systems with Losses ............................................................ 29

2.1 Introduction ............................................................................................ 29

2.2 The Erlang Loss System ..................................................................... 30

2.3 The Erlang Loss Formula ................................................................... 31

Chapter 3

Queueing Systems Allowing Waiting................................................. 41

3.1 Introduction ............................................................................................ 41

3.2 The Erlang Delay System ................................................................... 41

x An Elementary Introduction to Queueing Systems

3.3 The Distribution Function of the Waiting Time ....................... 46

3.4 Little’s Formula...................................................................................... 50

Chapter 4

The Engset Loss and Delay Systems .................................................. 59

4.1 Introduction ............................................................................................ 59

4.2 The Engset Loss System ..................................................................... 59

4.3 The Arriving Customer’s Distribution for the Engset Loss

System ....................................................................................................... 62

4.4 The Offered Load and Carried Load in the Engset

Loss System ............................................................................................. 64

4.5 The Engset Delay System................................................................... 65

4.6 The Waiting Time Distribution Function for the Engset

Delay System .......................................................................................... 66

4.7 The Mean Waiting Time in the Engset Delay System ............ 67

4.8 The Offered Load and Carried Load in the Engset Delay

System ....................................................................................................... 68

Chapter 5

Queueing Systems with a Single Server ........................................... 71

5.1 Introduction ............................................................................................ 71

5.2 The M/M/1 Queue ................................................................................ 71

5.3 The M/G/1 Queue and the Pollaczek-Khinchin Formula

for the Mean Waiting Time ............................................................... 74

5.4 The M/G/1 Queue with Vacations ................................................. 83

5.5 The M/G/1 Queue with Priority Discipline................................ 83

(A) The HOL Non-Preemptive Priority System ....................... 84

(B) The Preemptive Priority System .............................................. 88

5.6 The GI/M/1 Queue ............................................................................... 90

(A) The Probability of Waiting and the Mean Waiting

Time ........................................................................................................... 94

(B) The Waiting Time Distribution Function ............................. 95

Bibliography

Index