Computational complexity of uncapacitated multi-echelon production planning problems

Recently there has been a flurry of research in the area of production planning for multi-echelon production-distribution systems with deterministic non-stationary demands and no capacity constraints. A variety of algorithms have been proposed to optimally solve these problems, with varying success. This paper investigates the issue of computational complexity of the problem for all commonly studied product structures, i.e. the single item, the serial system, the assembly system, the one-warehouse-N-retailer system, the distribution system, the joint replenishment system, and the general production-distribution system. Polynomial time algorithms are available for the single-item, serial and assembly system. The authors prove that the remaining problems are NP-complete.