Lecture Notes in Economics and Mathematical Systems
              Volume              6632013
Performance Analysis of Closed Queueing NetworksAuthors:

• Svenja Lagershausen
• …show all 1hide
  

ISBN: 978-3-642-32213-6 (Print) 978-3-642-32214-3  (Online)



Series: Lecture Notes in Economics and Mathematical Systems, Vol. 663

Lagershausen, Svenja

2013, XXIII, 169 p. 49 illus., 5 in color.

ISBN 978-3-642-32214-3

  Immediately available per PDF-download (no DRM, watermarked)

• About this book
  

•                                         First exact analysis of closed production systems for finite-capacity networks with general processing times
•                                         High-quality vector graphics support the main text
•                                         Extensive examples to add value to the content​
  

This book deals with the performance analysis of closed queueing networks with general processing times and finite buffer spaces. It offers a detailed introduction to the problem and a comprehensive literature review. Two approaches to the performance of closed queueing networks are presented. One is an approximate decomposition approach, while the second is the first exact approach for finite-capacity networks with general processing times. In this Markov chain approach, queueing networks are analyzed by modeling the entire system as one Markov chain. As this approach is exact, it is well-suited both as a reference quantity for approximate procedures and as extension to other queueing networks. Moreover, for the first time, the exact distribution of the time between processing starts is provided.

Contents
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Motivation .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Closed Queueing Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1 Assumptions.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1 Relevant Theorems.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Exact Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.1 Product-Form Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.2 Non-Product-Form Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 Approximate Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3.1 Exponential Distribution and Infinite Buffer Capacity. . . . . . . . 26
3.3.2 Exponential Distribution and Finite Buffer Capacity . . . . . . . . . 28
3.3.3 General Distribution and Infinite Buffer Capacity . . . . . . . . . . . . 33
3.3.4 General Distribution and Finite Buffer Capacity .. . . . . . . . . . . . . 42
4 Decomposition Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.1 Algorithm.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.1.1 Outer Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.1.2 Inner Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2 Numerical Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5 Markov-Chain Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.1 Overview of the Markov-Chain Approach .. . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2 Phase-Type Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.2.1 Selection of Phase-Type Distributions . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2.2 Two-Moment Parameter Fit of Selected
Phase-Type Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
vii
viii Contents
5.3 Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3.1 Phase-Type and Original Representation . . . . . . . . . . . . . . . . . . . . . . 71
5.3.2 Markov-Chain Odels of CQN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.4 State Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.4.1 Generation of Workpiece Allocations . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.4.2 Generation of Phases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.4.3 Generation of Blocking Statuses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.5 Transition Rates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.5.1 Derivation of the Global Balance Equations . . . . . . . . . . . . . . . . . . 91
5.5.2 Construction of the Transition Rate Matrix . . . . . . . . . . . . . . . . . . . 111
5.6 Solution of the Linear System of Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.6.1 GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.6.2 Examples .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.7 Performance Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.7.1 Aggregation of the Markov-Chain Steady-State
Probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.7.2 Calculation of the Performance Measures .. . . . . . . . . . . . . . . . . . . . 121
5.7.3 Examples .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.8 Runtime Performance and Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . 124
6 Distribution of the Time Between Processing Starts . . . . . . . . . . . . . . . . . . . . . 131
6.1 Motivation .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.2 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.3 Assignment of the Markov-Chain States to Subsets. . . . . . . . . . . . . . . . . . . 135
6.4 Components of the Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
6.4.1 Probabilities of Transition into Non-active States . . . . . . . . . . . . . 137
6.4.2 Time Spent in a Non-active State . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
6.4.3 Transition Probabilities Between Non-active States . . . . . . . . . . 142
6.5 Determination of the Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
6.5.1 General Phase-Type Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.5.2 Transition Rate Matrix of the TBPSi -Distribution . . . . . . . . . . . . 144
6.6 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
6.6.1 Exponential Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
6.6.2 Cox-2 Distribution .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
6.7 Numerical Study of the Parameter Influences on CV 2.TBPSi / . . . . . . 151
6.7.1 Influence of the Processing Rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
6.7.2 Influence of c2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
6.7.3 Influence of the Buffer Capacity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
7 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161