Heuristics for capacity planning problems with congestion

Motivated by a problem in the semiconductor industry, we develop improved formulations for the problem of planning capacity acquisition and deletion over time when resources are subject to congestion, motivated by a problem in the semiconductor industry. We use nonlinear clearing functions to relate the expected output of a production resource in a planning period to the expected work in process (WIP) inventory level. Exploiting the properties of the clearing function allows us to formulate the single workcenter problem as a shortest path problem. This forms the basis for two greedy constructive heuristics and a Lagrangian heuristic for the multistage problem. The latter procedure also provides lower bounds on the optimal value. We present computational experiments showing that the proposed heuristics obtain high-quality solutions in modest CPU times.