exupero's blog
RSSApps

The penny game and Kingman's formula

In an earlier post I argued that lower utilization at non-bottleneck stations shortens how long pennies spend on our simulated manufacturing line. That's expressed more mathematically by Kingman's formula:

𝔼(Wq) is the expected wait time at each station, and ρ is the station's utilization. As utilization increases, so does the wait time, but it increases non-linearly:

0%10%20%30%40%50%60%70%80%90%100%0102030405060708090100ρρ/(1-ρ)

When the station's utilization is below 80%, service is all but immediate. Above 85%, however, wait times increase significantly.

τ is the mean service time, and ca and cs are coefficients of arrival and service times, calculated as their respective standard deviation divided by their mean. In the penny game, all three are determined by rolling dice, so if I understand them correctly, they should be constants. If you know differently, please email me.

Kingman's formula doesn't fully describe completion times in the penny game, of course. It was written to describe the behavior of a single-station queue, and the penny game simulates multiple queues arranged in sequence. Looking at the formula, though, I don't see any reason that one station taking longer to finish a penny would cause the next station to take longer as well. Wait times don't seem to compound. Thus, to describe time to completion in the penny game, all we may need to do is add up the wait times in each individual queue:

Despite the apparent independence between station wait times in this formula, there is a hidden dependency between stations: their utilization. When one station is flooded with pennies, its utilization is high and it produces lots of work for the next station, which eventually floods the next station with pennies, causing the cycle to repeat all the way down the line. The above expression doesn't capture it, but stations' utilization rates are coupled.