Simulation Optimization Library: Throughput Maximization

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Throughput Maximization in a Flow Line

Overview
- This is a stochastic optimization problem to maximize the long-run output of an n-stage production line with limited buffer space and a fixed total service capacity.
- Each stage has one server. The job supply for Stage 1 is unlimited; the service time at Stage i is exponentially distributed with rate ri.
- Buffers before Stations 2…n have capacities b2, b3, ..., bn. If a buffer is full, Station i−1 is blocked (production blocking), so a finished job cannot be released from Station i−1.
- The goal is to choose buffer allocations and service rates to maximize throughput (average output per unit time) in the long run.
- The total buffer space and total service rate are limited: sum(bi) ≤ B and sum(ri) ≤ R. Buffers are integers; service rates can be integers or reals.

How to design the system
- One simple approach is: set b2,…,bn as large as possible under the buffer limit, and assign any leftover capacity to the highest-numbered stations (one unit per buffer). Choose uniform (equal) service rates as a baseline.
- If you want multiple starting points for optimization, you can sample initial buffers and rates.
- For continuous service rates, sample from the simplex {r ≥ 0 : r1 + … + rn ≤ R}. A practical method is:
- Generate n−1 random values from Uniform(0, R), sort them to create a partition, and set ri = U(i) − U(i−1) with U(0) = 0 and U(n) = R.
- Do a similar sampling for buffer spaces (allowing 0).

Simulation and measuring throughput
- Each simulation run (replication) consists of:
- Warm-up: release 2000 jobs starting from an empty system.
- Measurement: record the time T needed to release the next 50 jobs.
- Throughput for that replication is estimated as 50 / T (jobs per unit time).
- The time metric is the simulated time, and the throughput of interest is the long-run (limiting) throughput, not a short warm-up estimate.
- Buffer space is counted as the number of jobs waiting to be processed (the current job is not included). You count how many jobs remain at each stage to determine when a job leaves every stage.

Two example solutions (discrete service rates, moderate size)
- There are two known good solutions for the discrete-rate case:
1) Rates r = (6, 7, 7) with buffers b = (12, 8)
2) Rates r = (7, 7, 6) with buffers b = (8, 12)
- For both, the throughput is evaluated in the same way: via the long-run rate, using the time difference between releases of the 50th last and the last of the current 50 jobs.

Notes
- If you allow continuous service rates, you can generate diverse starting points by sampling from the rate simplex and then allocate buffers similarly.
- The objective is to maximize the long-run throughput, defined as the steady-state output rate, rather than a short-run or warm-up estimate.