Multi-item, multi-facility supply chain planning: models, complexities, and algorithms

We propose a planning model for products manufactured across multiple manufacturing faciliites sharing similar production capabilities. The need for cross-facility capacity management is most evident in high-tech industries that have capital-intensive equipment and a short technology life cycle. We propose a multicommodity flow network model where each commodity represents a product and the network structure represents manufacturing facilities in the supply chain capable of producing the products. We analyze in depth the product-level (single-commodity, multi-facility) subproblem when the capacity constraints are relaxed. We prove that even the general-cost version of this uncapacitated subproblem is NP-complete. We show that there exists an optimization algorithm that is polynomial in the number of facilities, but exponential in the number of periods. We further show that under special cost structures the shortest-path algorithm could achieve optimality. We analyze cases when the optimal solution does not correspond to a source-to-sink path, thus the shortest path algorithm would fail. To solve the overall (multicommodity) planning problem we develop a Lagrangean decomposition scheme, which separates the planning decisions into a resource subproblem, and a number of product-level subproblems. The Lagrangean multipliers are updated iteratively using a subgradient search algorithm. Through extensive computational testing, we show that the shortest path algorithm serves as an effective heuristic for the product-level subproblem (a mixed integer program), yielding high quality solutions with only a fraction (roughly 2%) of the computer time.