exupero's blog

The Penny Game

In his book The Goal, Eliyahu Goldratt described a simulation of a manufacturing line using match sticks and dice, though I believe one of his later books used pennies instead of match sticks. I've called the simulation "the penny game" for years, so I'll stick with that term for this series.

The simulation, in brief, is that we have a number of sequential stations on a manufacturing line, and each station's capacity to move pennies to the next station isn't fixed but is determined by a roll of a die. Our job is to optimize the line. To facilitate experimentation, we'll run simulations with code rather than rolling dice and moving pennies manually.

We'll represent our manufacturing line as a list of numbers. Each position in the list is a station, and each number is how many pennies the respective station has to work on:

(def initial-state
  {:stations (repeat 6 4)})
{:stations (4 4 4 4 4 4)}

As with any simulation, we need function to update the simulation's state. Ours will take the previous state and a list indicating how many pennies each station can process. The number of pennies actually processed, however, depends not only on the station's production capacity but also on how many pennies it has in its queue; no station can process more pennies than it has to work on. The output of each station is added to the next station's queue. Here's the update function:

(defn update-state [{:keys [stations]} [incoming & capacities]]
  (let [processed (map min stations capacities)
        new-stations (map (fn [queue outgoing incoming]
                            (-> queue
                                (- outgoing)
                                (+ incoming)))
                          (cons incoming processed))]
    {:incoming incoming
     :capacities capacities
     :processed processed
     :stations new-stations}))

Notice that the second argument to this function, representing station productivity, has an extra value prepended to the beginning of it. That value represents how many pennies are added to the first station's queue, which is why it's cons'd onto the list of processed pennies, to be used as input to the first station.

I've included the number of incoming pennies, the capacities of each station, and how many pennies each station processed so we can later check the logic and do some analysis.

We can simulate the manufacturing line using iterate and a random number generator:

(defn simulate
  [initial-state update-state iterations generate-capacities]
  (let [rng (java.util.Random. 10)
        roll #(.nextInt rng 1 7)]
    (take (inc iterations)
      (iterate #(update-state % (generate-capacities roll))

We increment the number of iterations because iterate produces a sequence whose first item is our initial state.

To simulate the line, we provide our initial state, a number of iterations to run, and a function which provides a list of the incoming pennies and how many pennies each station is capable of processing in this step:

(simulate initial-state update-state 1
  (fn [roll]
    (repeatedly 7 roll)))
({:stations (4 4 4 4 4 4)}
 {:incoming 4,
  :capacities (1 4 1 5 5 2),
  :processed (1 4 1 4 4 2),
  :stations (7 1 7 1 4 6)})

We can check the results: the first station had 4 pennies, could only proccess 1, then it received 4 from the pennies coming into the line, so it now has 7 pennies. The second station had 4 pennies, processed 4, then received 1 from the previous station's output, giving it 1 penny. And so on.

Since we're trying to optimize the line, let's run the simulation for 100 steps and see the total output of the final station, which gives us the overall production of the entire line:

(defn total-output [steps]
    (map #(-> % :processed last (or 0)))
    + steps))
  (simulate initial-state update-state 100
    (fn [roll]
      (repeatedly 7 roll))))

In the next post, we'll look at a metric in additional to total output that we should consider when optimizing our line.