An algorithm for optimal buffer placement in reliable serial lines

The optimal allocation of buffer capacity in unbalanced production lines wi th reliable but variable workstations is a complex and little-researched to pic. Analytic formulas for the throughput of these lines do not exist, so s imulation is the only practical alternative for estimating throughput. Exha ustive search over all possible buffer allocations quickly becomes impracti cal beyond short lines and few buffers. Thus an algorithm is needed to effi ciently find optimal or near-optimal allocations. We develop a simple searc h algorithm for determining the optimal allocation of a fixed amount of buf fer capacity in an n-station serial line. The algorithm, which is an adapta tion of the Spendley-Hext and Nelder-Mead simplex search algorithms, uses s imulation to estimate throughput for every allocation considered. An import ant feature of the algorithm is that the simulation run length is adjusted during the running of the algorithm to save simulation run time when high p recision in throughput estimates is not needed, and to ensure adequate prec ision when it is needed. We describe the algorithm and show that it can rel iably find the known optimal allocation in balanced lines. Then we test the ability of the algorithm to find optimal allocations in unbalanced lines, first for cases in which the optimal allocation is known, and subsequently for cases in which the optimal allocation is not known. We focus particular ly on lines with multiple imbalances in means and variances. In general, ou r algorithm proves highly efficient in finding a near-optimal allocation wi th short simulation run times. It also usually finds the true optimal alloc ation, but it is in the nature of this problem that many buffer allocations differ in throughput by small amounts that are difficult to resolve even w ith long simulation runs.