Deterministic Production Planning: Algorithms and Complexity

TLDR

Production planning problems with known demands over a finite horizon aim to minimize total costs, considering production, storage, set‑up costs, and capacity limits. The study investigates the computational complexity of these production planning problems. The authors describe and analyze several algorithms for solving these problems. They demonstrate that certain special cases are NP‑hard, implying no polynomial‑time solutions are likely.

Abstract

A class of production planning problems is considered in which known demands have to be satisfied over a finite horizon at minimum total costs. For each period, production and storage cost functions are specified. The production costs may include set-up costs and the production levels may he subject to capacity limits. The computational complexity of the problems in this class is investigated. Several algorithms proposed for their solution are described and analyzed. It is also shown that some special cases are NP-hard and hence unlikely to be solvable in polynomial time.