Download Queueing Theory by Ivo Adan, Jacques Resing ebook. Includes all important topics.

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/Er/1 queue 51
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