Queueing Systems Ivo Adan and Jacques Resing Department of Mathematics and Computing Science Eindhoven University of Technology P.O. Box 513, 5600 MB Eindhoven, The Netherlands March 26, 2015 Contents 1 Introduction 7 1.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Basic concepts from probability theory 11 2.1 Random variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Generating function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Laplace-Stieltjes transform . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4 Useful probability distributions . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4.1 Geometric distribution . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4.2 Poisson distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4.3 Exponential distribution . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4.4 Erlang distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4.5 Hyperexponential distribution . . . . . . . . . . . . . . . . . . . . . 15 2.4.6 Phase-type distribution . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5 Fitting distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.6 Poisson process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3 Queueing models and some fundamental relations 23 3.1 Queueing models and Kendall’s notation . . . . . . . . . . . . . . . . . . . 23 3.2 Occupation rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.3 Performance measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.4 Little’s law . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.5 PASTA property . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4 M/M/1 queue 29 4.1 Time-dependent behaviour . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.2 Limiting behavior . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.2.1 Direct approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2.2 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2.3 Generating function approach . . . . . . . . . . . . . . . . . . . . . 32 4.2.4 Global balance principle . . . . . . . . . . . . . . . . . . . . . . . . 32 3 4.3 Mean performance measures . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.4 Distribution of the sojourn time and the waiting time . . . . . . . . . . . . 33 4.5 Priorities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.5.1 Preemptive-resume priority . . . . . . . . . . . . . . . . . . . . . . 36 4.5.2 Non-preemptive priority . . . . . . . . . . . . . . . . . . . . . . . . 37 4.6 Busy period . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.6.1 Mean busy period . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.6.2 Distribution of the busy period . . . . . . . . . . . . . . . . . . . . 38 4.7 Java applet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5 M/M/c queue 43 5.1 Equilibrium probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 Mean queue length and mean waiting time . . . . . . . . . . . . . . . . . . 44 5.3 Distribution of the waiting time and the sojourn time . . . . . . . . . . . . 46 5.4 Java applet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 5.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 6 M/E /1 queue 51 r 6.1 Two alternative state descriptions . . . . . . . . . . . . . . . . . . . . . . . 51 6.2 Equilibrium distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 6.3 Mean waiting time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 6.4 Distribution of the waiting time . . . . . . . . . . . . . . . . . . . . . . . . 55 6.5 Java applet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 6.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 7 M/G/1 queue 61 7.1 Which limiting distribution? . . . . . . . . . . . . . . . . . . . . . . . . . . 61 7.2 Departure distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 7.3 Distribution of the sojourn time . . . . . . . . . . . . . . . . . . . . . . . . 66 7.4 Distribution of the waiting time . . . . . . . . . . . . . . . . . . . . . . . . 68 7.5 Lindley’s equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.6 Mean value approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 7.7 Residual service time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 7.8 Variance of the waiting time . . . . . . . . . . . . . . . . . . . . . . . . . . 72 7.9 Distribution of the busy period . . . . . . . . . . . . . . . . . . . . . . . . 73 7.10 Java applet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 7.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 8 G/M/1 queue 81 8.1 Arrival distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 8.2 Distribution of the sojourn time . . . . . . . . . . . . . . . . . . . . . . . . 85 8.3 Mean sojourn time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4 8.4 Java applet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 8.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 9 Priorities 89 9.1 Non-preemptive priority . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 9.2 Preemptive-resume priority . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 9.3 Shortest processing time first . . . . . . . . . . . . . . . . . . . . . . . . . 92 9.4 A conservation law . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 9.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 10 Variations of the M/G/1 model 99 10.1 Machine with setup times . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 10.1.1 Exponential processing and setup times . . . . . . . . . . . . . . . . 99 10.1.2 General processing and setup times . . . . . . . . . . . . . . . . . . 100 10.1.3 Threshold setup policy . . . . . . . . . . . . . . . . . . . . . . . . . 101 10.2 Unreliable machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 10.2.1 Exponential processing and down times . . . . . . . . . . . . . . . . 102 10.2.2 General processing and down times . . . . . . . . . . . . . . . . . . 103 10.3 M/G/1 queue with an exceptional first customer in a busy period . . . . . 105 10.4 M/G/1 queue with group arrivals . . . . . . . . . . . . . . . . . . . . . . . 106 10.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 11 Insensitive systems 113 11.1 M/G/∞ queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 11.2 M/G/c/c queue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 11.3 Stable recursion for B(c,ρ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 11.4 Java applet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 11.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Solutions to Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 5 6 Chapter 1 Introduction In general we do not like to wait. But reduction of the waiting time usually requires extra investments. To decide whether or not to invest, it is important to know the effect of the investment on the waiting time. So we need models and techniques to analyse such situations. In this course we treat a number of elementary queueing models. Attention is paid to methods for the analysis of these models, and also to applications of queueing models. Importantapplicationareasofqueueingmodelsareproductionsystems,transportationand stocking systems, communication systems and information processing systems. Queueing models are particularly useful for the design of these system in terms of layout, capacities and control. In these lectures our attention is restricted to models with one queue. Situations with multiple queues are treated in the course “Networks of queues.” More advanced techniques for the exact, approximative and numerical analysis of queueing models are the subject of the course “Algorithmic methods in queueing theory.” The organization is as follows. Chapter 2 first discusses a number of basic concepts and results from probability theory that we will use. The most simple interesting queueing model is treated in chapter 4, and its multi server version is treated in the next chapter. Models with more general service or interarrival time distributions are analysed in the chapters 6, 7 and 8. Some simple variations on these models are discussed in chapter 10. Chapter 9 is devoted to queueing models with priority rules. The last chapter discusses some insensitive systems. The text contains a lot of exercises and the reader is urged to try these exercises. This is really necessary to acquire skills to model and analyse new situations. 1.1 Examples Below we briefly describe some situations in which queueing is important. Example 1.1.1 Supermarket. How long do customers have to wait at the checkouts? What happens with the waiting 7 time during peak-hours? Are there enough checkouts? Example 1.1.2 Production system. A machine produces different types of products. What is the production lead time of an order? What is the reduction in the lead time when we have an extra machine? Should we assign priorities to the orders? Example 1.1.3 Data communication. In computer communication networks such as the Internet data packets are transmitted over links from one switch to the next. In each switch incoming packets can be buffered when the incoming demand exceeds the link capacity. Once the buffer is full, incoming packets will be lost. What is the packet delay at the switches? What is the fraction of packets that will be lost? What is a good size of the buffer? Example 1.1.4 Parking lot. They are going to make a new parking lot in front of a super market. How large should it be? Example 1.1.5 Assembly of printed circuit boards. Mounting vertical components on printed circuit boards is done in an assembly center consisting of a number of parallel insertion machines. Each machine has a magazine to store components. Whatistheproductionleadtimeoftheprintedcircuitboards? Howshouldthecomponents necessary for the assembly of printed circuit boards be divided among the machines? Example 1.1.6 Call centers of an insurance company. Questions by phone, regarding insurance conditions, are handled by a call center. This call center has a team structure, where each team helps customers from a specific region only. How long do customers have to wait before an operator becomes available? Is the number of incoming telephone lines enough? Are there enough operators? Pooling teams? Example 1.1.7 Toll booths. Motorists have to pay toll in order to pass a bridge. Are there enough toll booths? Example 1.1.8 Traffic lights. How do we have to regulate traffic lights such that the waiting times are acceptable? Example 1.1.9 Hospital emergency department. In a hospital emergency department patients arrive with various kinds of injuries and medical issues that require urgent treatment. How many nurses and doctors need to be on staff to provide patients with proper care in a timely manner? How many intensive care units are needed to hospitalize patients? 8 Example 1.1.10 Mobile communication network. Users download documents, visit websites and watch video clips on their laptops, tablets and smartphones. Should the data delivery for certain types of applications receive priority over others? How many access points need to be installed and where in order to ensure speedy data transfer? 9 10