Exact and heuristic procedures for capacity expansion problems with congestion

The problem of determining an optimal capacity expansion and contraction schedule over time for production resources subject to congestion is addressed. Previous to this work non-linear constraints based on expected queue length have been used to represent congestion, whereas concave clearing functions that capture the relationship between expected throughput and expected work in process inventory in a planning period are used in this paper. A column generation procedure that uses a previously developed pseudo-polynomial-time algorithm for the single-workcenter problem to generate new columns is proposed. The fractional solution obtained by column generation is then used to construct a feasible solution. Computational experiments on randomly generated test problems show that the procedure consistently produces near-optimal solutions in modest CPU times. The column generation formulation is also used to obtain lower bounds in an exact branch-and-bound algorithm, and it is shown that this new procedure is able to solve problems that are significantly larger than those possible with previous methods.