Simulation Optimization Library: Throughput Maximization

The problem of Throughput Maximization is a family of iterative stochastic optimization algorithms that attempt to find the maximum expected throughput in an n-stage Flow line. According to Pichitlamken et al. (2006), there are two solutions to the discrete service-rate moderate-sized problem. With an expected throughput (defined as the limiting throughput over a long time horizon, as opposed to the approximation induced through the need for a warm-up period and ratio-estimate as described under Measurement of time. Each simulation replication should consist of warming up the system with 2000 released jobs starting from an empty system, then recording the time T required to release the next 50 jobs, and estimating the throughput on this replication as 50=T jobs per unit time. Time is then measured in the number of simulation replications performed.

Problem statement

Consider an n-stage flow line with finite buffer storage in front of Stations 2, 3,..., n, denoted by b2, b3,..., bn, and an infinite number of jobs in front of Station 1. There is a single server at each station, and the service time at Station i is exponentially distributed with service rate ri, i = 1,..., n. If the buffer of Station i is full, then Station i-1 is blocked (production blocking), so that a finished job cannot be released from Station i-1, i = 2,..., n. The total buffer space and the service rates are limited. The goal is to find a buffer allocation and service rates such that the throughput (average output of the flow line per unit time) is maximized. One can optionally take the service rates as integers or as continuous variables. In either case the problem is still considered as integer-ordered because the buffer allocations are integers. The constraints are:

b₂+...+b_n≤ B r₁+r₂+...+r_n≤R

Recommended parameter settings

A moderate-sized problem is n = 3;B = 20;R = 20. A larger problem is n = 12;B = 80;R = 80.

Starting solution(s)

Take b₂=...=b_n as large as possible without violating the constraint. Allocate any residual buffer spaces to the largest-numbered stations (one per buffer). Similarly, choose uniform service rates. If multiple initial solutions are desired then sample the buffer spacings and service rates as follows. For continuous service rates, sample uniformly from the simplex {r≥0:r₁+r₂+...+r_n≤R}.This can be done by generating n-1 independent uniform random variables U₁,...,U_n-1on [0,R], ordering them so that U₍₁₎≤...≤U_(n-1), setting U₍₀₎=0 and U_(n)=R, and finally setting r_k=U_(k)-U_(k-1), k = 1,...,n. A similar procedure can be used for assigning the buffer spaces, which can be allowed to take the value 0.

Measurement of time

Each simulation replication should consist of warming up the system with 2000 released jobs starting from an empty system, then recording the time T required to release the next 50 jobs, and estimating the throughput on this replication as 50=T jobs per unit time. Time is then measured in the number of simulation replications performed.

Optimal solutions

We will consider buffer space as the number of pieces waiting to be worked on. i.e. the current job does not count as part of the buffer space Cycle through each job to determine the time at which it leaves every stage. There are 2 solutions to the discreteservice-rate moderate-sized problem, namely r = (6, 7, 7), b = (12, 8) and r = (7, 7, 6), b = (8, 12)with an expected throughput (defined as the limiting throughput over a long time horizon, as opposed to the approximation induced through the need for a warm-up period and ratio-estimate as described under "Measurement of Time").

Throughput = 50/(time last job released - time at which the 50th to last job was released)

Reported algorithm performance

None.