Simulation Tables by Hand

This section turns the ideas of lecture 1 into a skill you can do with a pencil: take a probability table, turn it into random-number intervals, and build a simulation table one customer (or one day) at a time. Everything a simulation program does, you will do here by hand, slowly enough to see every event.

Objectives

By the end of the section you should be able to:

• Turn a probability distribution into cumulative probabilities and random-number intervals.
• Read a given random number into a value: an inter-arrival time, a service time, or a category.
• Build a simulation table for a single-server queue, column by column.
• Compute the average waiting time, the average time a customer spends in the system, and the average idle time of the server.
• Handle scheduled arrivals in clock time, and problems with two independent random variables per day.
• Avoid the classic mistakes: interval boundaries, forgetting max(), the first customer, and units.

Where this sits in the course

Lecture 1 defines simulation as imitating the operations of a facility or process, usually via computer. The facility or process we study is the system: a collection of entities (people, parts, machines, servers) that act and interact together toward some end. To study it we make assumptions, logical and mathematical, and that set of assumptions is the model.

In this section the systems are a grocery counter, a dentist clinic and a factory. The model is the probability table we are given. The simulation is the table we fill in by hand.

All three problems are discrete event simulation models, the kind lecture 1 says most operational models are:

• Dynamic: we follow the system over time, customer after customer.
• Stochastic: arrivals and service times are random, drawn from probabilities.
• Discrete: the state changes only at separate points in time, when a customer arrives or departs.

The clock moves by next-event time advance: it starts at 0 and jumps from one event (an arrival or a departure) to the next, skipping periods of inactivity. Lecture 1 summarises what happens to each customer as:

Departure time = Arrival time + Service time + Delay time

Why do it by hand first?

A simulation program does exactly what our table does, only faster. Lecture 1 lists the components of such a program, and each one has a place in the hand table:

If you can fill the table correctly, you can later write the program and check its output against your table.

The core method: from probabilities to random-number intervals

Every problem in this section starts the same way. A random quantity (an inter-arrival time, a service time, a treatment type) is described by a table of values and probabilities. We need a rule that turns a given random number into one of those values, with each value coming up as often as its probability says.

The four-step recipe

1. List every possible value with its probability.
2. Add the probabilities down the table to get the cumulative probability.
3. Give each value a block of two-digit random numbers from 00 to 99, as many numbers as its probability in percent. Two digits give exactly 100 numbers, so a probability of 0.18 gets 18 of them.
4. Read each given random number: find the interval it falls in, and take that value.

The interval rule

For each value, the interval runs from the previous cumulative probability to just below this one:

Low end  = (previous cumulative) x 100
High end = (this cumulative) x 100 - 1

The last interval always ends at 99. If yours does not, a probability has been dropped or mis-added.

Worked example: the service times of Q1

Service times of 1 to 8 minutes have probabilities 0.10, 0.18, 0.22, 0.16, 0.14, 0.10, 0.05 and 0.05:

Service time 2 has previous cumulative 0.10 and cumulative 0.28, so its interval is 10 - 27. The number 28 is the first number of the next interval, service time 3. Note that 0.28 gives a high end of 27, not 28.

Reading numbers from this table:

The boundary numbers 27 and 28 are where most marks are lost. Always check both ends of an interval.

Equally likely values

When all values have the same probability, the intervals are equal blocks. The Q1 inter-arrival times, 1 to 10 minutes, are equally likely, so each gets 10% of the numbers: 00 - 09 for 1 minute, 10 - 19 for 2 minutes, and so on up to 90 - 99 for 10 minutes.

Two digits or three?

Two-digit numbers work whenever every probability is a whole percent. Lecture 1 has an example with eight equally likely inter-arrival times, each with probability 1/8 = 0.125. Three decimals need three-digit random numbers, 000 to 999, giving the intervals 000 - 124, 125 - 249, 250 - 374, and so on. Match the number of digits to the precision of the probabilities. Every problem in this section uses two digits.

The simulation table

A simulation table has one row per customer and one formula per column.

The formulas, as lecture 1 states them, for customer i:

Arrival(i)        = Arrival(i-1) + Inter-arrival(i)
Service start(i)  = max( Arrival(i), Service end(i-1) )
Service end(i)    = Service start(i) + Service time(i)
Waiting time(i)   = Service start(i) - Arrival(i)
Time in system(i) = Service end(i) - Arrival(i)
Idle time(i)      = Service start(i) - Service end(i-1)

The procedure for one customer

1. Read random number 1 into the inter-arrival time.
2. Add it to the previous arrival to get the arrival time.
3. Read random number 2 into the service time.
4. Service starts at the later of the arrival time and the previous customer's service end.
5. Add the service time to get the service end.
6. Fill in waiting time, time in system and idle time.

Finish a whole row before moving on: the next row needs this row's arrival and service end.

Why max()? Two cases

• The server is already free (the customer arrives after the previous service end). Service starts at the arrival. Waiting time is 0, and the server was idle for arrival minus previous end.
• The server is still busy (the customer arrives before the previous service end). Service starts at the previous end. The customer waits for previous end minus arrival, and idle time is 0.

So in every row at least one of waiting time and idle time is 0. Both are 0 when a customer arrives exactly as the previous one leaves.

From the table to the averages

Add each column and divide by the number of customers:

Average waiting time   = total waiting time   / number of customers
Average time in system = total time in system / number of customers
Average idle time      = total idle time      / number of customers

A built-in check: time in system = waiting time + service time in every row, so the same holds for the totals and the averages.

Q1: the grocery store

Problem. At a grocery store with one counter, customers arrive at random from 1 to 10 minutes apart (all inter-arrival times equally likely). Service times vary from 1 to 8 minutes with probabilities 0.10, 0.18, 0.22, 0.16, 0.14, 0.10, 0.05 and 0.05. Simulate 10 customers using the random numbers 92, 73, 02, 95, 31, 92, 75, 24, 23, 30 for inter-arrival times and 84, 10, 74, 53, 17, 79, 91, 67, 89, 38 for service times. For each customer find the arrival time, service start and end, waiting time, time in system and server idle time, then the averages.

Step 1: interval tables

The service-time intervals are the ones built in the worked example above: 00 - 09, 10 - 27, 28 - 49, 50 - 65, 66 - 79, 80 - 89, 90 - 94, 95 - 99 for 1 to 8 minutes.

Step 2: read the random numbers

Step 3: customer by customer

• Customer 1. Inter-arrival 10, so arrival = 0 + 10 = 10. Nobody is ahead, so service starts at 10 and ends at 10 + 6 = 16. Waiting time 0, time in system 16 - 10 = 6. The idle column is 0: the idle formula needs a previous customer's service end, and there is none. The exercise counts idle time between customers.
• Customer 2. Arrival = 10 + 8 = 18. Previous end 16, so start = max(18, 16) = 18, end = 18 + 2 = 20. Wait 0, time in system 2, idle 18 - 16 = 2.
• Customer 3. Arrival = 18 + 1 = 19. Previous end 20, so start = max(19, 20) = 20, end = 20 + 5 = 25. Wait 20 - 19 = 1, time in system 6, idle 0.
• Customer 4. Arrival = 19 + 10 = 29, previous end 25: start 29, end 33, wait 0, idle 4.
• Customer 5. Arrival = 29 + 4 = 33, previous end 33: start 33, end 35. Wait 0 and idle 0 (arrives exactly as customer 4 leaves).
• Customer 6. Arrival = 33 + 10 = 43, previous end 35: start 43, end 48, idle 8.
• Customer 7. Arrival = 43 + 8 = 51, previous end 48: start 51, end 58, idle 3.
• Customer 8. Arrival = 51 + 3 = 54, but the server is busy until 58: start 58, end 63, wait 4.
• Customer 9. Arrival = 54 + 3 = 57, server busy until 63: start 63, end 69, wait 6.
• Customer 10. Arrival = 57 + 4 = 61, server busy until 69: start 69, end 72, wait 8.

The last three customers show a queue forming: short inter-arrival times (3, 3, 4) against long service times, so each customer inherits the delay of the one ahead and the waits grow 4, 6, 8.

The complete simulation table

The averages

Average waiting time of a customer in the queue = 19 / 10 = 1.9 minutes
Average time a customer spends in the system    = 64 / 10 = 6.4 minutes
Average idle time of the server                 = 17 / 10 = 1.7 minutes

Check: the average service time is 45 / 10 = 4.5 minutes, and 1.9 + 4.5 = 6.4.

Reading the result: 4 of the 10 customers waited (customers 3, 8, 9 and 10), and the long waits all come at the end when arrivals bunch up. Ten customers is a small sample; a different set of random numbers would give a different table.

Extension: server utilization

Lecture 2 defines server utilization as the time the server is busy divided by the total simulation time. The server is busy for the sum of the service times, 45 minutes, and the last customer leaves at 72:

Utilization = 45 / 72 = 0.625 = 62.5%

Over the whole run from 0 to 72, busy time 45 plus idle time 27 makes 72. That 27 includes the first 10 minutes, before customer 1 arrived. The Q1 table does not count those 10 minutes, which is why its idle total is 17. When you solve a problem, say clearly which convention you use.

Q2: the dentist clinic

Problem. A dentist sees 6 patients. Simulation starts at 8:00; arrivals are scheduled, the first patient at 8:00 and then one every 45 minutes. Each patient needs one of five treatments, and which one is not known in advance: a random number decides it. Using the random numbers 40, 82, 11, 34, 25, 66, find each patient's treatment, arrival, departure and waiting time, and the average waiting time.

Scheduled arrivals

Lecture 2 notes that arrivals may occur at scheduled times, like booking to see a doctor, or at random. Here the arrival times are fixed by the schedule, so there is no random number for them: 8:00, 8:45, 9:30, 10:15, 11:00 and 11:45. Only the treatment, and therefore the service time, is random.

Step 1: intervals for the categories

Build the intervals in the order the problem lists the services:

Step 2: which treatment?

Note that 40 is Crown, not Filling: the Filling interval ends at 39.

Step 3: working in clock time

Add minutes and carry into hours: 8:00 + 60 minutes = 9:00, 10:15 + 45 minutes = 11:00, 11:45 + 20 minutes = 12:05.

• Patient 1 arrives at 8:00, the dentist is free, a crown takes 60 minutes: 8:00 to 9:00, wait 0.
• Patient 2 arrives at 8:45 while the dentist is busy until 9:00. The checkup runs 9:00 to 9:15, and the wait is 9:00 - 8:45 = 15 minutes.
• Patient 3 arrives at 9:30; the dentist has been free since 9:15 (idle for 15 minutes). Filling from 9:30 to 10:15, wait 0.
• Patient 4 arrives at 10:15 exactly as patient 3 leaves: 10:15 to 11:00, wait 0.
• Patient 5 arrives at 11:00 exactly as patient 4 leaves: 11:00 to 11:45, wait 0.
• Patient 6 arrives at 11:45 exactly as patient 5 leaves: cleaning from 11:45 to 12:05, wait 0.

The complete table

Average waiting time = 15 / 6 = 2.5 minutes

Q3: units produced and vehicles available

Problem. A manufacturing facility produces a random number of units per day, and a random number of vehicles is available for transportation at a station:

Use the random numbers 91, 73, 02, 95, 31, 93, 75, 24, 23, 30 for units produced and 84, 10, 74, 53, 17, 79, 91, 67, 89, 38 for vehicles available, over 10 working days. Find the average number of units produced per day and the average number of vehicles available per day.

No queue and no clock

Each day is independent of the day before, so there are no arrival or service-end columns. Each day has two random variables, each with its own interval table and its own list of random numbers. Never read a units random number from the vehicles table.

Step 1: both interval tables

Step 2: the simulation table

The averages

Average number of units produced per day    = 6300 / 10 = 630 units/day
Average number of vehicles available per day =   73 / 10 = 7.3 vehicles/day

A note on day 5. The printed solution of the exercise lists 5 vehicles on day 5, totals 72 and gives an average of 7.2 vehicles/day. Random number 17 falls in the interval 15 - 49, which is 6 vehicles (the interval 00 - 14, for 5 vehicles, ends at 14). With 6 vehicles on day 5 the total is 73 and the average is 7.3 vehicles/day. The units column is unaffected: 630 units/day stands.

Common mistakes

With intervals

• Boundary off by one. A cumulative probability of 0.28 ends the interval at 27, not 28.
• 00 and 99. 00 is the first number and 99 the last. There are 100 two-digit numbers, not 99.
• Wrong table. Reading a service random number from the inter-arrival table, or a units number from the vehicles table.
• Wrong order. Building the intervals in a different order from the problem's table changes which value each number gives.
• A real example. Day 5 of Q3: random number 17 read as 5 vehicles instead of 6 changed the average from 7.3 to 7.2.

In the table

• Forgetting max(). Starting a customer at the arrival time while the server is still busy with the previous customer.
• The first customer. Read the problem. In the lecture 1 example, customer 1 arrives at time 0 with no random number; in Q1, customer 1 arrives after the first inter-arrival time, at 10.
• Idle time before the first customer. Q1 records 0 for customer 1 and counts idle time between customers only. If you count the gap from time 0, say so.
• Units and clock time. 8:45 plus 60 minutes is 9:45. Waiting times are durations in minutes, not clock times.
• Averages. Divide by the number of customers (or days), not by the last clock time.

A self-check before you submit

1. The last interval of every interval table ends at 99.
2. In every row, time in system = waiting time + service time.
3. In every row, at least one of waiting time and idle time is 0.
4. Arrival times never decrease, and no service starts before the previous service end.
5. The totals are written under the columns, and the averages use the right count.

Practice problems

Allow about 30 minutes for all three. Answers are at the end of the page.

Practice 1: a copy center (about 15 minutes)

A copy center has one machine. Customers arrive 1 to 5 minutes apart, all equally likely. Service times are 1 to 5 minutes with probabilities 0.10, 0.25, 0.30, 0.20 and 0.15. Simulate 8 customers (customer 1 arrives after the first inter-arrival time, as in Q1) using:

• Random numbers for inter-arrival times: 85, 19, 98, 44, 53, 79, 52, 91
• Random numbers for service times: 64, 99, 70, 09, 60, 05, 56, 77

Find the average waiting time, the average time in the system, and the average idle time of the machine.

Practice 2: a car garage (about 10 minutes)

A garage takes 6 cars by appointment: the first at 9:00, then one every 40 minutes. The service each car needs is decided by a random number:

Random numbers: 35, 12, 95, 34, 65, 85.

Find each car's service start, service end and waiting time, the average waiting time, and the total idle time of the mechanic between cars.

Practice 3: a bakery (about 8 minutes)

A bakery receives a random number of delivery orders per day, and a random number of drivers is available:

• Random numbers for orders: 09, 55, 10, 89, 49, 80, 50, 26
• Random numbers for drivers: 70, 24, 95, 25, 69, 90, 00, 89

Simulate 8 days and find the average number of orders per day and the average number of drivers available per day.

Key takeaways

1. Probabilities become cumulative probabilities, then random-number intervals that end at 99.
2. Each random number is read through its own interval table.
3. Arrival = previous arrival + inter-arrival; service start = max(arrival, previous service end).
4. Waiting time = start - arrival; time in system = end - arrival; idle time = start - previous end.
5. Total each column, then divide by the number of customers or days.
6. Scheduled arrivals remove one random variable; independent days remove the clock. The lookup step never changes.

Answers

Practice 1

Interval tables:

Simulation table:

Average waiting time   =  8 / 8 = 1 minute
Average time in system = 32 / 8 = 4 minutes
Average idle time      =  4 / 8 = 0.5 minutes

Check: the average service time is 24 / 8 = 3 minutes, and 1 + 3 = 4. Watch random number 64: it is still service time 3, because the interval for 3 minutes is 35 - 64.

Practice 2

Average waiting time = 60 / 6 = 10 minutes

The mechanic is idle for 10 minutes (9:30 to 9:40) and 20 minutes (10:00 to 10:20), 30 minutes in total. The boundary numbers are the trap here: 34 is Oil change, 35 Tire change, 65 Brake repair and 85 Full service. The last car finishes at 13:50, because services longer than the 40-minute gap (70, 50 and 70 minutes) push every later car back.

Practice 3

Average number of orders per day   = 290 / 8 = 36.25 orders/day
Average number of drivers per day  =  28 / 8 = 3.5 drivers/day