Multifacility-Type Capacity Expansion Planning: Algorithms and Complexities

We examine several variations of a capacity expansion model with multiple facility types, and with the flexibility for converting capacity from one facility type to another. Applications can be found in communication networks and production facilities. The models include costs of expansions, conversions, excess capacities and capacity shortages, and assume cost functions that are either linear or concave. We find the optimal solution by exploiting properties of extreme flows in networks and employing a dynamic programming algorithm. Specializing our results permits us to obtain different model variations by imposing certain conditions on the cost functions, and to derive the computational complexities for these variations. Typically, applications require extensive sensitivity studies that may use up substantial computer resources. Our analysis unifies previous work, extends the results, and provides intuition concerning the difficulties involved in applying the models.