Deterministic Production Planning: Algorithms and Complexity
研究一类生产规划问题，在有限时间内满足已知需求并最小化总成本，分析其计算复杂性，描述并分析多种求解算法，指出某些特例是NP难的。
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.