Fundamentals of Queueing Theory (eBook)

John F. Shortle, James M. Thompson, Donald Gross, Carl M. Harris (Autoren)

eBook Download: EPUB

2018 | 5. Auflage
John Wiley & Sons (Verlag)
978-1-118-94353-3 (ISBN)

Infos

The definitive guide to queueing theory and its practical applications-features numerous real-world examples of scientific, engineering, and business applications

Thoroughly updated and expanded to reflect the latest developments in the field, Fundamentals of Queueing Theory, Fifth Edition presents the statistical principles and processes involved in the analysis of the probabilistic nature of queues. Rather than focus narrowly on a particular application area, the authors illustrate the theory in practice across a range of fields, from computer science and various engineering disciplines to business and operations research. Critically, the text also provides a numerical approach to understanding and making estimations with queueing theory and provides comprehensive coverage of both simple and advanced queueing models. As with all preceding editions, this latest update of the classic text features a unique blend of the theoretical and timely real-world applications. The introductory section has been reorganized with expanded coverage of qualitative/non-mathematical approaches to queueing theory, including a high-level description of queues in everyday life. New sections on non-stationary fluid queues, fairness in queueing, and Little's Law have been added, as has expanded coverage of stochastic processes, including the Poisson process and Markov chains.

• Each chapter provides a self-contained presentation of key concepts and formulas, to allow readers to focus independently on topics relevant to their interests

• A summary table at the end of the book outlines the queues that have been discussed and the types of results that have been obtained for each queue

• Examples from a range of disciplines highlight practical issues often encountered when applying the theory to real-world problems

• A companion website features QtsPlus, an Excel-based software platform that provides computer-based solutions for most queueing models presented in the book.

Featuring chapter-end exercises and problems-all of which have been classroom-tested and refined by the authors in advanced undergraduate and graduate-level courses-Fundamentals of Queueing Theory, Fifth Edition is an ideal textbook for courses in applied mathematics, queueing theory, probability and statistics, and stochastic processes. This book is also a valuable reference for practitioners in applied mathematics, operations research, engineering, and industrial engineering.

John F. Shortle, PhD, is Professor in the Department of Systems Engineering and Operations Research at George Mason University.

James M. Thompson is an Enterprise Architect at the Federal Home Loan Mortgage Corporation.

Donald Gross, PhD, is Professor emeritus, The George Washington University, and was Distinguished Research Professor of Operations Research and Engineering at George Mason University.

The late Carl M. Harris, PhD, was BDM International Professor and the founding chair of the Systems Engineering and Operations Research Department at George Mason University.

Inhalt

Preface ix

Acknowledgments xi

About the Companion Website xiii

1 Introduction 1

1.1 Measures of System Performance 2

1.2 Characteristics of Queueing Systems 4

1.3 The Experience of Waiting 9

1.4 Little's Law 10

1.5 General Results 19

1.6 Simple Bookkeeping for Queues 22

1.7 Introduction to the QtsPlus Software 26

Problems 27

2 Review of Stochastic Processes 35

2.1 The Exponential Distribution 35

2.2 The Poisson Process 39

2.3 Discrete-Time Markov Chains 49

2.4 Continuous-Time Markov Chains 62

Problems 69

3 Simple Markovian Queueing Models 73

3.1 Birth-Death Processes 73

3.2 Single-Server Queues (M=M=1) 77

3.3 Multiserver Queues (M=M=c) 90

3.4 Choosing the Number of Servers 97

3.5 Queues with Truncation (M=M=c=K) 100

3.6 Erlang's Loss Formula (M=M=c=c) 105

3.7 Queues with Unlimited Service (M=M=1) 108

3.8 Finite-Source Queues 109

3.9 State-Dependent Service 115

3.10 Queues with Impatience 119

3.11 Transient Behavior 121

3.12 Busy-Period Analysis 126

Problems 127

4 Advanced Markovian Queueing Models 147

4.1 Bulk Input (M¯[X]=M=1) 147

4.2 Bulk Service (M=M[Y ]=1) 153

4.3 Erlang Models 158

4.4 Priority Queue Disciplines 172

4.5 Retrial Queues 191

Problems 204

5 Networks, Series, and Cyclic Queues 213

5.1 Series Queues 215

5.2 Open Jackson Networks 221

5.3 Closed Jackson Networks 229

5.4 Cyclic Queues 243

5.5 Extensions of Jackson Networks 244

5.6 NonJackson Networks 246

Problems 248

6 General Arrival or Service Patterns 255

6.1 General Service, Single Server (M=G=1) 255

6.2 General Service, Multiserver (M=G=c=_,M=G=1) 290

6.3 General Input (G=M=1, G=M=c) 295

Problems 306

7 General Models and Theoretical Topics 313

7.1 G=Ek=1, G¯[k]=M=1, and G=PHk=1 313

7.2 General Input, General Service (G=G=1) 320

7.3 Poisson Input, Constant Service, Multiserver (M=D=c) 330

7.4 Semi-Markov and Markov Renewal Processes in Queueing 332

7.5 Other Queue Disciplines 337

7.6 Design and Control of Queues 342

7.7 Statistical Inference in Queueing 353

Problems 361

8 Bounds and Approximations 365

8.1 Bounds 366

8.2 Approximations 378

8.3 Deterministic Fluid Queues 392

8.4 Network Approximations 400

Problems 411

9 Numerical Techniques and Simulation 417

9.1 Numerical Techniques 417

9.2 Numerical Inversion of Transforms 433

9.3 Discrete-Event Stochastic Simulation 446

Problems 469

References 475

Appendix A: Symbols and Abbreviations 487

Appendix B: Tables 495

Appendix C: Transforms and Generating Functions 503

C.1 Laplace Transforms 503

C.2 Generating Functions 510

Appendix D: Differential and Difference Equations 515

D.1 Ordinary Differential Equations 515

D.2 Difference Equations 531

Appendix E: QtsPlus Software 537

E.1 Instructions for Downloading 540

Index 541

Textauszug

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" communities. 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 stores 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?

The answer is simple: There is more demand for service than there is facility for service available. Why is this so? There may be many reasons; for example, there may be a shortage of available servers, it may be infeasible economically for a business to provide the level of service necessary to prevent waiting, or there may be a space limit to the amount of service that can be provided. Generally these limitations can be removed with the expenditure of capital, and to know how much service should then be made available, one would need to know answers to such questions as “How long must a customer wait?” and “How many people will form in the line?” Queueing theory attempts to answer these questions through detailed mathematical analysis.

The earliest problems studied in queueing theory were those of telephone traffic congestion. The pioneer investigator was the Danish mathematician A. K. Erlang, who, in 1909, published “The Theory of Probabilities and Telephone Conversations.” In later works he observed that a telephone system was generally characterized by either (1) Poisson input, exponential holding (service) times, and multiple channels (servers), or (2) Poisson input, constant holding times, and a single channel. Work on the application of the theory to telephony continued after Erlang. In 1927, E. C. Molina published his paper “Application of the Theory of Probability to Telephone Trunking Problems,” which was followed one year later by Thornton Fry's book Probability and Its Engineering Uses, which expanded much of Erlang's earlier work. In the early 1930s, Felix Pollaczek did some further pioneering work on Poisson input, arbitrary output, and single- and multiple-channel problems. Additional work was done at that time in Russia by Kolmogorov and Khintchine, in France by Crommelin, and in Sweden by Palm. The work in queueing theory picked up momentum rather slowly in its early days, but accelerated in the 1950s, and there has been a great deal of work in the area since then.

There are many valuable applications of queueing theory including traffic flow (vehicles, aircraft, people, communications), scheduling (patients in hospitals, jobs on machines, programs on a computer), and facility design (banks, post offices, amusement parks, fast-food restaurants). Most real problems do not correspond exactly to a mathematical model, and increasing attention is being paid to complex computational analysis, approximate solutions, simulation, and sensitivity analyses.

1.1 Measures of System Performance

Figure 1.1 shows a typical queueing system: Customers arrive, wait for service, receive service, and then leave the system. Some customers may leave without receiving service, perhaps because they grow tired of waiting in line or perhaps because there is no room to enter the service facility in the first place.

Figure 1.1 A typical queueing system.

Note that the term “customer” is often used throughout this text in a general sense and does not necessarily imply a human customer. For example, a customer could be a ball bearing waiting to be polished, an airplane waiting in line to take off, or a computer program waiting to be run.

What might one like to know about the effectiveness of a queueing system? Generally there are three types of system responses of interest: (1) Some measure of the waiting time that a typical customer might endure, (2) some measure of the number of customers that may accumulate in the queue or system, and (3) a measure of the idle time of the servers. Since most queueing systems have stochastic elements, these measures are often random variables, so their probability distributions - or at least their expected values - are sought.

Regarding waiting times, there are two types - the time a customer spends in the queue and the total time a customer spends in the system (queue plus service). Depending on the system being studied, one may be of more interest than the other. For example, if we are studying an amusement park, it is the time waiting in the queue that makes the customer unhappy. But if we are dealing with machines that require repair, then it is the total down time (queue wait plus repair time) that we wish to keep as small as possible. Throughout this book, the average waiting time of a typical customer in queue is denoted as Wq and the average waiting time in the system is denoted as W.

Correspondingly, there are two customer accumulation measures - the number of customers in the queue and the total number of customers in the system. The former is of interest if we desire to determine a design for waiting space (e.g., the number of seats to have for customers waiting in a hair-styling salon), while the latter may be of interest for knowing how many machines may be unavailable for use. The average number of customers in the queue is denoted as Lq and the average number of customers in the system is denoted as L. Finally, idle-service measures can include the percentage of time any particular server may be idle or the time the entire system is devoid of customers.

The task of the queueing analyst is generally one of two things - to determine some measures of effectiveness for a given process or to design an “optimal” system according to some criterion. To do the former, one must determine waiting delays and queue lengths from the given properties of the input stream and the service procedures. For the latter, the analyst might want to balance customer-waiting time against the idle time of servers according to some cost structure. If the costs of waiting and idle service can be obtained directly, they can be used to determine the optimum number of servers. To design the waiting facility, it is necessary to have information regarding the possible size of the queue. There may also be a space cost that should be considered along with customer-waiting and idle-server costs to obtain the optimal system design. In any case, the analyst can first try to solve this problem by analytical means; if these fail, he or she may use simulation. Ultimately, the issue generally comes down to a trade-off between better customer service and the expense of providing more service capability, that is, determining the increase in investment of service for a corresponding decrease in customer delay.

1.2 Characteristics of Queueing Systems

A quantitative evaluation of a queueing system requires a mathematical characterization of the underlying processes. In many cases, six basic characteristics provide an adequate description of the system:

1. Arrival pattern of customers
2. Service pattern of servers
3. Number of servers and service channels
4. System capacity
5. Queue discipline
6. Number of service stages

The standard notation for characterizing a queueing system based on the first five characteristics will be described shortly (Section 1.2.7).

1.2.1 Arrival Pattern of Customers

In usual queueing situations, the process of arrivals is stochastic, and it is thus necessary to know the probability distribution describing the times between successive customer arrivals (interarrival times). A common arrival process is the Poisson process, which will be described in Section 2.2. It is also necessary to know whether customers can arrive simultaneously (batch or bulk arrivals), and if so, the probability distribution describing the size of the batch.

Another factor is the manner in which the pattern changes with time. An arrival pattern that does not change with time (i.e., the probability distribution describing the input process is time-independent) is called a stationary arrival pattern. One that is not time-independent is called nonstationary. An example of a system with a nonstationary arrival pattern might be a restaurant where more customers tend to arrive during the lunch hour than during other times of the day. Many of the models in this text assume a stationary arrival process.

It is also necessary to know the reaction of a customer upon arrival to the system. A customer may decide to wait no matter how long the queue becomes, or, if the queue is too long, the customer may decide not to enter the system. If a customer decides not to enter the queue upon arrival, the customer is said to have balked. A customer may enter the queue, but after a time lose patience and decide to leave. In this case, the customer is said to have reneged. In the event that there are two or more parallel waiting lines, customers may switch from one to another, that is, jockey for position. These three situations are all examples of queues with impatient customers.

1.2.2 Service...

Produkt-Details

• Erscheint lt. Verlag: 2.5.2018
• Reihe/Serie: Wiley Series in Probability and Statistics
• Reihe/Serie: Wiley Series in Probability and Statistics
• Reihe/Serie: Wiley Series in Probability and Statistics
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Allgemeines / Lexika
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Statistik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik
• Schlagworte: approximations for queueing networks • Betriebswirtschaft • Betriebswirtschaft u. Operationsforschung • Business & Management • introduction to queuing theory</p> • <p>queuing theory • Management Science/Operational Research • markov chains in queuing theory • numerical inversion of transforms • probability and queuing theory • Production Operations Management • Produktionssteuerung • Queuing models • queuing theory • queuing theory and networking • queuing theory and software design • queuing theory applications • queuing theory aviation applications • queuing theory business applications • queuing theory engineering applications • queuing theory explained • queuing theory for traffic control • queuing theory in computer science • queuing theory in management science • queuing theory in operations research • queuing theory in systems analysis • queuing theory problems • queuing theory statistical processes • queuing theory stochastic processes • queuing theory telecommunications applications • Retrial Queues • Statistics • Statistik • stochastic models in queueing theory • Warteschlange • Warteschlangentheorie • Wirtschaft u. Management
• ISBN-10: 1-118-94353-8 / 1118943538
• ISBN-13: 978-1-118-94353-3 / 9781118943533