Computational Complexity of the Capacitated Lot Size Problem
研究实际中常见成本结构下、有容量限制的批量问题的计算复杂性，识别出多项式时间可解和NP难的问题类别，并给出高效解法。
In this paper we study the computational complexity of the capacitated lot size problem with a particular cost structure that is likely to be used in practical settings. For the single item case new properties are introduced, classes of problems solvable by polynomial time algorithms are identified, and efficient solution procedures are given. We show that special classes are NP-hard, and that the problem with two items and independent setups is NP-hard under conditions similar to those where the single item problem is easy. Topics for further research are discussed in the last section.