Dynamics and Queueing Networks

Uncover the dynamics of the best duo from 2014-2015 in soccer alongside insights into unlucky days. Delve into the interplay of soccer teams and queueing networks, exploring contributions, scoring assistance, and system queue times. Understand the impact of dependence among single queues in series and the reduction method in tandem systems. Analyze Jackson networks under Markovian assumptions and ASIA systems. Discover the concept of intrinsic ratios in understanding contribution queue time.

• Duo Dynamics
• Queueing Networks
• Soccer Teams
• System Queue Time
• Markovian Assumptions

suza_7 Follow

Uploaded on Feb 18, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. The Best Duo 2014 - 2015 1

2. Unlucky Days Sometimes, things may go in the other direction 2

3. Soccer Teams vs. Queueing Networks In soccer teams Contribution Scoring Assistance Chemistry In queueing networks Dependence 3

4. Dependence among Single Queues in Series Kan Wu 4

5. Dependence in Queueing Networks Dependence among stations Positive: reduce system queue time Negative: increase system queue time Queue time classification Actual queue time The queue time performance in appearance The total score a player get Contribution queue time The authentic contribution to the system The effort a player contributed to the total score of the team 5

6. Reduction Method Friedman tandem queue (1965) Constant service time (cs = 0) System queue time is solely determined by the bottleneck = Bottleneck QT when it is a single server system 1 i = = sc 1/ n = System QT QT i QTBN = 100 QT1 = 20 QTBN = 80 BN 1 BN Actual QT1 = 20 Contribution QT1 = 0 Contribution QTBN = 100 Fully coupled system Actual QTBN = 80 6

7. Jackson Network Under Markovian assumptions Exponential service time (cs = 1) with Poisson arrivals Each station behaves independently in the steady state QTBN = 100 QT1 = 20 QTBN = 100 BN 1 BN Actual QT1 = 20 Contribution QT1 = 20 Contribution QTBN = 100 Actual QTBN = 100 ASIA (all see initial arrivals) system 7

8. ASIA and Fully Coupled Systems N single sever in series S3 S1 S2 SN ASIA and Fully coupled systems A QT ( ca1) 1 Actual queue times 1 1 BN 1 BN A A QT QT QT QT k QT 1 BN i BN i 1 = = 1 i 1 i A k QT 1 ( ca1) ( ca1) m BN1 BNk BN1 A QT 0 0 A QT BN 1 ( ca1) n Contribution queue times N 8

9. General Situation In general, contribution queue time can be obtained through the concept of intrinsic ratios. ??? ???? ???? ???? , 2 ? ?. ??= 100% 90% 80% 70% Intrinsic Ratio 60% 50% 40% 30% 20% 10% 0% 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% Utilization 9

10. Contribution Queue Time Conservation of queue time Contribution is relative to the ASIA queue times Computation of Contribution Factor 10

11. Dependence in Tandem Queues Uni-Direction dependence Decentralized dispatching policy with local information The states of downstream stations have no impact on the dispatching decisions of the upstream stations. S1 S2 S3 SN Diffusion vs. Blocking Diffusion: actual queue time increases due to the upstream stations. Blocking: actual queue time decreases due to the upstream stations. Quantified through contribution queue time 11

12. Case study: Diffusion on Bottlenecks Poisson arrivals with mean 33 1/3 min Service times: 20 23 25 28 30 SCVs: 8 0.8 0.8 0.8 0.4 Bottleneck is the last station S3 S1 S2 S3 S5 Actual queue times: 135.18 124.96 101.67 172.46 220.35 ASIA system QTs: 135.00 46.07 67.50 132.30 189.00 12

13. Diffusion on Bottlenecks First 2 Stations Actual queue times: 135.18 124.96 ASIA system QTs: 135.00 46.07 Contribution QTs: 214.07 46.07 S1 S2 160 Diffused from station 1 to 2 (78.89) ASIA system queue time 140 120 100 Minutes 78.89 80 135.18 60 40 46.07 20 0 QT1 QT2 13

14. Diffusion on Bottlenecks First 3 Stations Actual queue times: 135.18 124.96 101.67 ASIA system QTs: 135.00 46.07 67.50 Contribution QTs: 242.19 52.12 67.50 S1 S2 S3 Diffused from station 2 to 3 (6.05) Diffused from station 1 to 3 (28.12) 160 Diffused from station 1 to 2 (78.89) ASIA system queue time 140 120 100 6.05 Minutes 78.89 28.12 80 135.18 60 40 67.50 46.07 20 0 14 QT1 QT2 QT3

15. Diffusion on Bottlenecks All 5 Stations Actual queue times: 135.18 124.96 101.67 172.46 220.35 ASIA system QTs: 135.00 46.07 67.50 132.30 189.00 Contribution QTs: 284.86 61.31 79.39 140.06 189.00 Diffused from station 4 to 5 (7.76) Diffused from station 3 to 5 (4.40) 250 Diffused from station 2 to 5 (3.40) Diffused from station 1 to 5 (15.79) Diffused from station 3 to 4 (7.49) Diffused from station 2 to 4 (5.79) 7.76 4.40 Diffused from station 1 to 4 (26.88) Diffused from station 2 to 3 (6.05) 3.40 200 15.79 Diffused from station 1 to 3 (28.12) Diffused from station 1 to 2 (78.89) ASIA system queue time 7.49 5.79 150 26.88 Minutes 100 6.05 189.00 78.89 28.12 132.30 135.18 50 67.50 46.07 0 QT1 QT2 QT3 QT4 QT5 15

16. Block on Bottlenecks All 5 Stations Service times: 20 23 25 28 30 with Poisson arrivals & SCVs 0.25 for all Actual queue times: 18.75 22.88 30.37 63.47 116.73 ASIA system QTs: 18.75 32.00 46.88 91.88 168.75 Contribution QTs: 2.17 7.20 17.48 56.59 168.75 180 Station 5 blocked by station 4 (35.28) Station 5 blocked by station 3 (10.90) Station 5 blocked by station 2 (4.49) Station 5 blocked by station 1 (1.35) 160 35.28 Station 4 blocked by station 3 (18.50) Station 4 blocked by station 2 (7.62) 140 Station 4 blocked by station 1 (2.29) Station 3 blocked by station 2 (12.69) 10.90 120 4.49 Station 3 blocked by station 1 (3.82) Station 2 blocked by station 1 (9.12) 1.35 100 Actual queue time Minutes 18.50 80 7.62 2.29 60 116.73 40 12.69 3.82 63.47 9.12 20 30.37 22.88 18.75 16 0 QT1 QT2 QT3 QT4 QT5

17. Second Moment Result on TOC Service times: 28 26 24 22 30 with SCVs 0.8 Poisson arrivals If the SCVs can be reduced by half, which one should be the 1st? S1 S2 S3 S3 S5 ??(0,0) ??(1,0.5) ??(2,0.5) ??(3,0.5) ??(4,0.5) ??(5,0.5) 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.95 1.63 7.90 18.36 33.23 54.12 84.08 129.37 208.70 388.79 652.69 1.33 6.62 15.57 28.48 46.39 72.13 111.49 179.53 336.96 573.47 1.38 6.88 16.17 29.54 48.27 75.15 116.70 188.95 357.86 610.73 1.43 7.07 16.64 30.35 49.52 77.27 119.78 194.80 368.96 625.14 1.48 7.24 17.04 30.97 50.58 78.79 122.08 197.70 374.53 635.92 1.42 7.05 16.59 30.20 49.15 76.28 116.80 186.96 340.62 548.87 : Service time SCV of station i is reduced by p (in percentage) 17

18. Second Moment Result on TOC 90 Diffused from station 4 to 5 (3.79) Diffused from station 3 to 5 (4.80) 80 3.79 Diffused from station 2 to 5 (5.34) 4.80 70 Diffused from station 1 to 5 (4.36) 5.34 4.36 Diffused from upstream stations to 4 (7.84) 60 Diffused from upstream stations to 3 (7.77) 50 Minutes Diffused from station 1 to 2 (2.39) 40 ASIA system queue time 59.58 30 2.39 7.77 20 7.84 27.31 24.24 10 18.92 13.21 0 QT1 QT2 QT3 QT4 QT5 18

19. Summary Dependence among tandem queues Actual queue time vs. contribution queue time Blocking and diffusion effects Dependence cannot be captured by the product-form and Brownian networks Theory of constraint Utilization should be strictly less than 1 in the long run Total sojourn/cycle time is the true limit Improving the performance of the system bottleneck may not be the most effective place to reduce system cycle time Improvement should start from the system bottleneck or upstream stations 19

20. ~ Just like human beings, a server has its life in a queueing network. ~ Thank you 20

21. Defense Acquisition Program Assembly Batching Dispatching Shift Schedule 21

22. Approximate Model for System Cycle Time 1 1 = + + BN i CT f PT BN i i f 1 1 i BN BN BN i i / 1 1 k k + + ' 3 ( 1) BN k n k PT 1 2 f 1 1 / k 3 3 BN BN 1 1 k = + + BN k k PT 1 2 f 1 k 3 3 BN BN k1: BN k2 : Variability of the (n - 1) non- bottleneck (in ASIA systems) k3: Non-bottleneck capacity 600 ST=30 ST=27 500 ST=25 ST=23 400 ST=20 300 200 100 22 100% 0 0% 10% 20% 30% 40% 50% 60% 70% 80% 90%

23. Regression Results 1900 k1 = 0.356 k2 = 422.951 k3 = 14.636 G/G/1 1700 Simulation 1500 3-Parameter Model Cycle Time (Hours) YAN's Model 1300 1100 BN Cap = 13.7 900 G/G/1 model 700 500 1 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% = + . BN CT k PT Utilization 1 f 1 10% BN BN G/G/1 Errors 3-Parameter Model Errors 5% YAN s model Yang, Ankenman and Nelson (2007) YAN's Model Errors 0% Error % 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% -5% + + 2 c c x c x x = c 0 1 2 ( , , ) CT x . p -10% )p (1 23 -15% Utilization

24. Model for Multiple-Server Stations k1: by historical bottleneck queue time in heavy traffic. by Sakasegawa (1977) QT 1) 1 + 2( m 1 BN = BN BN (1 ) m BN BN BN k3: capacity of the 2nd bottleneck, i.e. min , i k i = BN 3 k2: by historical factory cycle time 1) 1 + 2( m 2 1) 1 + 2( m m k 1 1 BN + + 2 3 BN CT k k PT 1 2 f (1 ) m m k 2 3 BN BN BN 1 m k 2 3 24

25. System with Multiple Servers Simulation k2 Model Input Rate (per day) Utilization CT (min) 761.1 761.2 761.2 761.6 762.2 763.3 765.3 768.4 774.0 785.1 818.2 892.8 95% CI 0.07 0.04 0.03 0.03 0.03 0.03 0.03 0.03 0.02 0.04 0.12 0.43 k2 k2_Extrapolation -2313.1 -1622.6 -932.0 -241.5 449.0 1139.5 1830.0 2520.6 3211.1 3901.6 4592.1 5015.3 CT (min) 761.0 761.0 761.0 761.0 761.4 762.1 763.7 766.8 772.7 785.1 818.2 882.7 Error 0.00% -0.02% -0.04% -0.07% -0.11% -0.16% -0.20% -0.22% -0.17% 0.00% 0.00% -1.12% 20 40 60 80 100 120 140 160 180 200 220 232 8.2% 16.3% 24.5% 32.6% 40.8% 49.0% 57.1% 65.3% 73.4% 81.6% 89.8% 94.8% 2325.8 2202.2 1269.8 1765.9 2157.9 2615.4 3011.7 3330.0 3610.7 3901.6 4592.1 5459.6 m = 5 k1 = 0.087 k3 = 248.276 950 1) 1 + 2( m 1 BN BN CT k Simulation 1 (1 ) m 900 BN BN BN k2 Model 1) 1 + 2( m 850 Cycle Time 2 m k 1 800 + + 2 3 k PT 2 f m k 2 3 1 750 m k 2 3 700 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 25 Utilization

26. The Intrinsic Gap and Intrinsic Ratio Intrinsic Gap (IG): The queue time difference between the ASIA and BSIA systems. Intrinsic Gap QT in ASIASystem QT in BSIASystem = . Intrinsic Ratio (IR): QT in ASIA Actual QT QT in BSIA System Intrinsic Gap IG = Actual QT . Intrinsic Ratio QT in BSIA If cs = 0 => actual QT = QT in BSIA => IR is 0 In Jackson networks => actual QT = QT in ASIA system => IR is 1 0 26

27. Structures of STQB ( 1, cs1) ( 2, cs2) ( , ca1) ( , ca2) 1 BN + 2 a 2 s 1 c c = A 1 2 2 QT ASIA: 2 2 1 2 2 + + 2 a 2 s 2 a 2 s c c c c 1 1 = B BSIA: 1 2 1 1 2 1 QT 2 2 1 2 1 2 2 1 1 + 2 a 2 s 1 c c Intrinsic Gap: = = 1 1 1 IG QT A QT 1 2 1 2 1 1 QT2 B QT QT Intrinsic Ratio: = 2 2 IR IG B QT 2 r 27

28. Simulation: Near-Linearity of the IR in STQB 100% 90% 80% 70% Intrinsic Ratio 60% 50% 40% 30% 20% 10% For different (m1, cs1, cs2) combinations 0% 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% Utilization STQB with Poisson Arrivals (with cs< 1) 10B ~ 100B data points in heavy traffic 28

29. Robustness & Heavy Traffic Property in STQB IG = QT1 QT2 1 BN 600 100% QT QT1 A B QT QT 2 IG QT as 500 = QT2 2 2 0 80% % QT 400 2 2 Queue Time 60% 1 Ratio 2 300 QT QT IG QT IG = 40% 1 200 QT2 in ASIA 2 2 20% 100 = QT IG QT2 0 0% QT2 in BSIA 0% 20% 40% 60% 80% 100% BN Utilization M/M/1 queues for 1/ 1 = 25, 1/ 2 = 30 (BN) 29 0

30. Two Important Properties of STQB 1. The intrinsic ratio is approximately linear across most traffic intensities Nearly-Linear Relationship 2. Robustness in heavy traffic Approximation A (1 ) QT QT y IG 2 2 2 + + 2 a 2 s 2 a 2 s 1 1 c c c c = (1 ) 1 2 1 1 2 1 y 2 2 1 2 1 2 2 1 1 30

31. Approximate Model for STQB A (1 ) QT QT y IG 2 2 2 + + 2 a 2 s 2 a 2 s 1 1 c c c c = (1 ) 1 2 1 1 2 1 y 2 2 1 2 1 2 2 1 1 Let y2 = cs1 + + 2 s 2 s 1 1 1 1 c c (1 ) 2 1 2 1 QT c 2 1 s 2 1 2 1 2 2 1 1 Compared with simulation Errors = 3.3% (when cs < 1, arrival process is Poisson) vs. 11.0% for QNA and 13.1% for QNET 31 Back