23-Ind-A6 Systems Simulation · December 2017

Question 6 of 8: Non-Preemptive Priority Queue: Hand Simulation

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

National Exams — December 2017 — 98-Ind-A6 Systems Simulation. Three-hour, closed-book exam; one of two permitted calculators (Sharp or Casio), two 8.5″×11.0″ aid sheets (both sides). Format: eight questions of equal value (10 marks each); candidates complete SIX of the EIGHT (only the first six as they appear in the answer book are marked). All eight questions are solved below for completeness (the paper's own Q6 is printed with an orphan leading "6." followed by "2. Consider an M/M/1 system…" and is answered as the paper's sixth question). Common Discrete/Continuous Distribution tables, Student-t and Chi-square tables were supplied with the exam; the values below are the same table values obtained by direct computation.

Reference texts: Banks, Carson, Nelson & Nicol, Discrete-Event System Simulation (5th ed., Pearson) — random-number/random-variate generation, input data analysis, output analysis (replications), comparing alternative systems, queueing simulation, and the simulation study life cycle.

Question 6 — Non-Preemptive Priority Queue: Hand Simulation (10 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. A single server, non-preemptive priority: whenever the server frees up, it picks the highest-priority customer currently waiting (FCFS within a priority class). Five arriving customers:

Customer	Priority	Interarrival	Arrival	Service Time
1	High	—	0	0.7
2	Low	0.3	—	1.0
3	Low	0.5	—	0.8
4	High	0.3	—	1.0
5	Low	1.2	—	0.5

Find. (a) the completed Start/End-Service table; (b) mean waiting time for the two High-priority customers; (c) time-average queue length (waiting only, both priorities pooled in one physical line).

Approach. Chain the interarrival times into absolute arrival times, then hand-step the single server: at each service completion, serve the highest-priority customer among those already arrived and waiting (ties broken by earliest arrival).

Arrival times. $A_1=0$; $A_2=0+0.3=0.3$; $A_3=0.3+0.5=0.8$; $A_4=0.8+0.3=1.1$; $A_5=1.1+1.2=2.3$.
Customer 1 (High, arrives at 0, server idle). Starts immediately: Start$=0.0$, End$=0.0+0.7=0.7$.
Server frees at 0.7. Only Customer 2 (Low) has arrived and is waiting $\Rightarrow$ served next: Start$=0.7$, End$=0.7+1.0=1.7$.
Server frees at 1.7. Waiting: Customer 3 (Low, arrived 0.8) and Customer 4 (High, arrived 1.1). High priority pre-empts the queue order (not the customer in service) $\Rightarrow$ Customer 4 served next: Start$=1.7$, End$=1.7+1.0=2.7$.
Server frees at 2.7. Waiting: Customer 3 (Low, since 0.8) and Customer 5 (Low, arrived 2.3). Both Low $\Rightarrow$ FCFS $\Rightarrow$ Customer 3 next: Start$=2.7$, End$=2.7+0.8=3.5$.
Server frees at 3.5. Only Customer 5 remains: Start$=3.5$, End$=3.5+0.5=4.0$.

Customer	Priority	Arrival	Start Service	End Service
1	High	0.0	0.0	0.7
2	Low	0.3	0.7	1.7
3	Low	0.8	2.7	3.5
4	High	1.1	1.7	2.7
5	Low	2.3	3.5	4.0

(b) Average waiting time, High-priority. Customer 1 waits $0.0-0.0=0$; Customer 4 waits $1.7-1.1=0.6$. $$\overline{W}_{High} = \frac{0+0.6}{2} = \boxed{0.3}.$$

(c) Average queue length (both priorities, single physical line, waiting only). Tracking the number of customers waiting (excludes whoever is currently in service) against the clock over the whole $[0,4.0]$ run and time-weighting:

Interval	Waiting	Duration
[0, 0.3)	0	0.3
[0.3, 0.7)	1	0.4
[0.7, 0.8)	0	0.1
[0.8, 1.1)	1	0.3
[1.1, 1.7)	2	0.6
[1.7, 2.3)	1	0.6
[2.3, 2.7)	2	0.4
[2.7, 3.5)	1	0.8
[3.5, 4.0)	0	0.5

$$L_q = \frac{1}{T}\sum (\text{level}\times\text{duration}) = \frac{4.1}{4.0} = \boxed{1.025\ \text{customers}}.$$

Quantity	Result
Average waiting time, High priority	0.3
Average queue length (waiting-only, pooled)	1.025

Check: "average queue length" is computed as the time-weighted number WAITING (excluding whoever is in service), the standard $L_q$ definition; the number IN SYSTEM ($L$, including the one in service) would instead average $1.025 + 700/4000\cdot1 \approx$ a higher figure since the server is busy for the full run — $L_q$ is used here since the question asks specifically about the shared "queue".

Concept & Theory

Topic. Hand (trace-driven) discrete-event simulation of a non-preemptive priority single-server queue.

Key relations. Non-preemptive priority: the server, once started on a customer, finishes it; only the WAITING-line order is priority-based. Time-weighted average $L_q = \frac{1}{T}\int_0^T Q(t)\,dt$.

Why this works. Advancing the clock event-by-event (arrivals and service completions) and re-evaluating "who is the highest-priority customer currently waiting" at each service completion is exactly the event-scheduling algorithm a coded simulation would execute; a hand trace of 5 customers is small enough to verify by exhaustive listing.

Common pitfall. Assuming priority is preemptive (i.e. that a High-priority arrival interrupts a Low-priority customer already in service) — the question states priority applies only "when a high priority customer is waiting" for the NEXT service, not mid-service; also, forgetting FCFS tie-breaking within a priority class (Customer 3 must go before Customer 5 once both are Low and waiting).

Source. Banks, Carson, Nelson & Nicol, Discrete-Event System Simulation, ch. 2 (hand simulation of queueing systems), ch. 6 (priority queueing disciplines).

← Question 5 Next: Question 7 →