Chapter 5Exam Weight: HIGHEST WEIGHT (Midterm 2024 Q2 = 20/30 pts, Midterm 2025 Q3 = 20/40 pts)Lec 5 Slides 1–75Lab 4Hagag Ch3-1..7Midterms 2024 & 2025

Queueing Systems (Single, Multi-Server & Tandem)

أنظمة الطوابير (خادم واحد، متعدد، ومتسلسل)

Queueing system characteristics, Kendall notation A/B/c/N/K, customer behaviors (balk/renege/jockey), single-server & parallel multi-server (Able/Baker) tables, tandem networks (Clinic & Petrol midterms), and performance metrics.

مكونات الطوابير وترميز Kendall، سلوكيات العميل، جداول محاكاة Single-Server و Multi-Server (Able & Baker)، الشبكات المتتالية (Tandem زي العيادة والبنزينة في الميدترم)، ومقاييس الأداء.

Chapter Mastery0% (0/3 sections · 0/4 checks)

Scope: Assoc. Prof. Ayman Ghoneim (FCAI — Cairo University)

What you'll lock down in this chapter

Describe the 5 queueing characteristics, Kendall notation A/B/c/N/K, and balking/reneging/jockeying.
Build a complete Single-Server simulation table and compute $W_q$ , $P(\text{Wait})$ , $W_{\text{waiters}}$ , $P(\text{Idle})$ , Utilization, and $W_s$ .
Apply parallel multi-server dispatching rules (Able & Baker tie-breaker: Able if both idle, else earliest free).
Trace Tandem/Sequential queues (Midterm 2024 Clinic & Midterm 2025 Petrol Station) where Stage 1 End = Stage 2 Arrival.
Use both Midterm [0,1) RN < CDF mapping and Slide/Lab 01–00 RD mapping cleanly without off-by-one mistakes.

Section 5.1Core Concepts

Queueing Characteristics, Behavior & Kendall Notation

عناصر الطابور، سلوك العميل، وترميز Kendall

Mark Section Mastered

5 Characteristics & Customer Behavior

الـ 5 مكونات الأساسية وسلوك العملاء

A queueing system is specified by: (1) Calling Population (finite vs. infinite), (2) Arrival Process (inter-arrival distribution), (3) Service Mechanism (# of servers & service time distribution), (4) System Capacity (finite vs. infinite), and (5) Queue Discipline (FIFO, LIFO, SIRO, SPT, PR).

Balk: sees a long line and refuses to join.
Renege: joins the line, waits too long, and leaves before service.
Jockey: switches from one parallel line to a shorter one.
Kendall Notation A / B / c / N / K: A = arrival dist (M = Markov/Exponential), B = service dist, c = servers, N = max system capacity (default ∞), K = population size (default ∞).

شرح عربي — كلام الدكتور

أي نظام طوابير بيتحدد بـ 5 حاجات: عدد العملاء المحتملين (Calling Population)، نمط الوصول، طريقة الخدمة وعدد السيرفرات، سعة المكان، وقانون الطابور (FIFO الأسبق أولاً، LIFO الأخير أولاً، SPT الأقصر خدمة أولاً، PR الأولوية).

Balk: شاف الزحمة ومادخلش الطابور أصلاً.
Renege: دخل الطابور وزهق فمشي قبل دوره.
Jockey: ساب صف وراح وقف في صف تاني أسرع.
Kendall A/B/c/N/K: M يعني Markov (أسّي Exponential) في الوصول أو الخدمة، و c عدد السيرفرات.

Section 5.2Formula Reference

Single-Server Simulation Table & Performance Metrics

جدول السيرفر الواحد ومقاييس الأداء

Mark Section Mastered

Core Concept

Row-by-Row Clock Logic & Metrics

قواعد الحساب صف بصف ومقاييس الكفاءة

For customer i, Arrival(i) = Arrival(i-1) + IA(i). Service cannot begin until BOTH the customer has arrived AND the server is free: Start(i) = max(Arrival(i), End(i-1)). Wait(i) = Start(i) - Arrival(i), Idle(i) = max(0, Arrival(i) - End(i-1)), End(i) = Start(i) + Dur(i), System(i) = End(i) - Arrival(i).

Notice Wait(i) and Idle(i) can NEVER both be positive on the same customer!
Always compare experimental averages against theoretical distribution means E[X] = ∑ x·P(X=x) (e.g., Lec 5 Grocery Store & Midterm 2024 Q2d).

شرح عربي — كلام الدكتور

القاعدة الذهبية في الجدول: الخدمة مش هتبدأ غير لما العميل يوصل والسيرفر يفضى، يعني Start(i) = max(Arrival(i), PrevEnd). لو العميل وصل بدري يستنى: Wait = Start - Arrival. لو السيرفر فضي بدري يقعد فاضي: Idle = max(0, Arrival - PrevEnd).

خلي بالك: مستحيل لنفس العميل يكون في Wait > 0 و Idle > 0 في نفس الوقت!
في الامتحان دايماً بيطلب تقارن المتوسط التجريبي من الجدول بالمتوسط النظري ∑ x·P(x).

Queueing Performance Metrics

Formula

قوانين قياس أداء الطابور

Average Waiting Time (All

N

)

W_q = \frac{\sum \text{Wait}_i}{N}

Wait Probability

P(\text{Wait}) = \frac{N_{\text{waiters}}}{N}

Average Wait of Waiters

W_{\text{waiters}} = \frac{\sum \text{Wait}_i}{N_{\text{waiters}}}

Server Utilization & Idle Share

\text{Util} = \frac{\sum \text{Dur}_i}{T_{\text{end}}}, \qquad P(\text{Idle}) = \frac{\sum \text{Idle}_i}{T_{\text{end}}}

Watch denominators carefully!

W_q

and

W_s

divide by ALL customers

N

;

W_{\text{waiters}}

divides ONLY by

N_{\text{waiters}}

; Utilization &

P(\text{Idle})

divide by Total Simulation End Time!

Section 5.3Midterm #1 Topic

Parallel Multi-Server (Able & Baker) vs. Tandem Queues (Exams!)

السيرفرات المتوازية (Able & Baker) vs الشبكات المتسلسلة (الميدترم!)

Mark Section Mastered

Midterm Exam Radar

Midterm 2024 · Q2(b–d)15 ptsView

Simulate 4 patients through Nurse → Doctor → Admin (fixed 2 min), compute wait/clinic time/service averages vs. theoretical.

15 درجة: جدول 4 مرضى في 3 مراحل + متوسطات الانتظار والخدمة ومقارنة بالنظري.

Midterm 2025 · Q3(b–d)14 ptsView

Simulate 4 cars at Fuel Pump + conditional Tires Service (RN < 0.4), waits, utilization % of Tires.

14 درجة: جدول 4 عربيات + احتمال التحويل للكاوتش + نسبة استغلال عامل الكاوتش.

Parallel Multi-Server Rule: Able & Baker

حالة الـ Parallel: مين ياخد المكالمة في Able & Baker؟

In a parallel multi-server queue (like Able & Baker or bank tellers), each customer needs only ONE server. Dispatching rule: (1) If Able is free at arrival (ableFree ≤ arr), choose Able; (2) else if Baker is free (bakerFree ≤ arr), choose Baker; (3) if BOTH are busy, choose whichever finishes EARLIER (break ties in favor of Able!).

شرح عربي — كلام الدكتور

في الـ Parallel (زي الكول سنتر Able و Baker أو شبابيك البنك)، العميل بيدخل لـ سيرفر واحد بس. القاعدة: لو Able فاضي يشتغل فوراً؛ لو مشغول و Baker فاضي يروح لـ Baker؛ لو الاتنين مشغولين يستنى اللي يخلص الأول (ولو خلصوا في نفس اللحظة، Able ليه الأولوية).

Exam Trap

Tandem / Sequential Queues (Midterm 2024 Clinic & 2025 Petrol!)

حالة الـ Tandem / Sequential: وصول المرحلة التانية = خروج الأولى!

In BOTH Midterm 2024 (Nurse → Doctor → Fixed 2-min Admin) and Midterm 2025 (Fuel Pump → 40% Tires), servers are in SERIES, not parallel! Crucial link: Stage 2 Arrival Time = Stage 1 Service End Time (zero travel time unless stated). If a car skips Tires (RN ≥ 0.4), the Tires server state stays untouched!

Check t = 0 vs Customer 1 arrival carefully! Midterm 2024 Clinic starts Customer 1 at t = 10; Midterm 2025 Petrol starts Car 1 at t = 2; Lab 4 starts at 08:00 (t = 0).
On Midterms, RNs are decimals in [0, 1): compare RN < CDF! (e.g., Midterm 2025 explicitly states 'if RN < 0.4, car visits tires service').

شرح عربي — كلام الدكتور

في ميدترم 2024 (ممرضة ← دكتور ← موظف ثابت دقيقتين) وميدترم 2025 (طرمبة بنزين ← كاوتش باحتمال 0.4)، السيرفرات ورا بعض مش متوازية! يعني وقت خروج العميل من المرحلة الأولى هو بالظبط وقت وصوله للمرحلة التانية. ولو عربية ماراحتش للكاوتش (RN ≥ 0.4)، مابتلمسش وقت انتهاء عامل الكاوتش!

ركز جداً في وقت وصول أول عميل! في عيادة 2024 المريض الأول وصل عند t = 10 (فالممرضة عندها Idle = 10 من الأول!)، وفي بنزينة 2025 أول عربية وصلت عند t = 2.
في الميدترم الأرقام العشوائية كسور في [0, 1)، فبنقارن بـ RN < CDF (مفيش 01–100).

Say This, Not That

Don't Say / Trap

Average Wait of Those Who Wait = ∑Wait / Total Customers N.

Say This Instead

$W_q = \frac{\sum \text{Wait}}{N}$ , whereas Average Wait of Waiters $= \frac{\sum \text{Wait}}{N_{\text{waiters}}}$ (only customers with $\text{Wait} > 0$ ).

Mixing $N$ and $N_{\text{waiters}}$ is the #1 calculation slip in Queueing summary questions.

لو 4 بس استنوا من أصل 7، متوسط انتظار المنتظرين بيتقسم على 4 مش على 7!

Say This, Not That

Don't Say / Trap

Map Midterm decimal RN = 0.25 using 01–100 inclusive rules or RN <= CDF.

Say This Instead

Use strict half-open intervals RN < CDF (so 0.00 ≤ RN < 0.25 maps to the first 0.25 bucket; RN = 0.25 moves to the next bucket).

Confirmed by Midterm 2025 Q3 ('less than 0.4') and continuous [0,1) uniform generation.

في امتحانات د. أيمن الأرقام [0, 1) والقاعدة الصريحة هي أقل من (RN < CDF)، يعني لو الرقم 0.4 بالظبط يدخل في الفئة اللي بعدها!

Interactive Simulation LabCh 5

Queueing & Clinic/Petrol Sandbox

متتبع طوابير الانتظار والمخطط الزمني

Ch 5 Interactive Lab: Queueing Network & Gantt Stepper

3-Stage Tandem Queue: Nurse -> Doctor -> Admin (constant 2m), FCFS at every stage.

Ch 5

Clock t = 0m / 66mCompleted: 0/6

NurseIDLE

Queue:Empty

Served so far: 0

DoctorIDLE

Queue:Empty

Served so far: 0

Admin (2m)IDLE

Queue:Empty

Served so far: 0

Live Service Gantt Timeline0m — 66m

Nurse

Doctor

Admin (2m)

Cust #	IAT	Arrival	Route / Stages	Wait	Departure	System Time
#1	—	10	Nurse: 10–18Doctor: 18–26Admin: 26–28	0m	28m	18m
#2	10	20	Nurse: 20–25Doctor: 26–34Admin: 34–36	1m	36m	16m
#3	10	30	Nurse: 30–32Doctor: 34–38Admin: 38–40	2m	40m	10m
#4	5	35	Nurse: 35–40Doctor: 40–48Admin: 48–50	0m	50m	15m
#5	10	45	Nurse: 45–47Doctor: 48–52Admin: 52–54	1m	54m	9m
#6	5	50	Nurse: 50–52Doctor: 52–64Admin: 64–66	0m	66m	16m

Avg Wait Time (Full Run)

0.67 min

Avg System Time

14.00 min

Makespan (Last Departure)

66 min

Instant Micro-Checks0/4 passed

Test your grasp before moving on

Wrong answers are automatically logged to your Weak Topics on the Coverage & Progress dashboard until you pass them.

Check 1

A customer arrives at a bank, sees 12 people waiting, and walks away without entering the queue. What is this behavior called?

عميل شاف الطابور طويل فلف ومشي من غير ما يدخل. ده اسمه إيه؟

Check 2

Customer 3 arrives at t = 12, and the server finishes Customer 2 at t = 13. When does Customer 3 start service, and what are Wait(3) and Idle(3)?

العميل 3 وصل عند t=12، والسيرفر خلص اللي قبله عند t=13. يبدأ إمتى و Wait و Idle بكام؟

Check 3

Over 45 minutes total simulation, 7 customers have

\sum \text{Wait} = 31\text{ min}

, 4 customers waited, and

\sum \text{Idle} = 3\text{ min}

. What is

W_{\text{waiters}}

في 7 عملاء مجموع انتظارهم 31 دقيقة و4 بس منهم انتظروا. إيه هو Average Wait of Those Who Wait؟

Check 4

In a Tandem queue (Nurse → Doctor), Patient 2 finishes with the Nurse at t = 25, while the Doctor is busy until t = 22. When does Patient 2 arrive at and start with the Doctor?

في طابور متسلسل (ممرضة ← دكتور)، المريض 2 خلص مع الممرضة عند t=25، والدكتور فاضي من t=22. يوصل للدكتور إمتى ويبدأ إمتى؟

30-Second Recap

Read these bullets right before entering the exam hall.

1Start(i) = max(Arr(i), PrevEnd); Wait(i) = Start(i) - Arr(i); Idle(i) = max(0, Arr(i) - PrevEnd).
2Check denominators: $W_q$ uses $N$ , $W_{\text{waiters}}$ uses $N_{\text{waiters}}$ , Utilization & $P(\text{Idle})$ use Total Simulation Time.
3Parallel (Able/Baker): Able wins if idle or tied; otherwise earliest available server.
4Tandem (Clinic/Petrol): Stage 2 Arrival = Stage 1 Departure. Midterm [0,1) RNs use RN < CDF!

ملخص ٣٠ ثانية بالعربي:

Start = max(Arrival, PrevEnd)، ومستحيل Wait و Idle الاتنين يبقوا أكبر من صفر لنفس العميل.
ركز في المقام: $W_{\text{waiters}}$ بيتقسم على عدد المنتظرين بس، والـ Utilization على الوقت الكلي.
في Able/Baker لو الاتنين فاضيين أو خلصوا سوا، Able ياخد العميل.
في الـ Tandem: نهاية المرحلة الأولى = بداية وصول التانية، وأرقام الميدترم بنقارنها بـ RN < CDF.

Ready to drill Chapter 5 questions?

10curated concept & written questions for this chapter.

Practice Chapter 5 (10)Browse Questions