An O(T2) Algorithm for the NI/G/NI/ND Capacitated Lot Size Problem
研究了一类容量动态批量问题，其中设置成本非增、单位持有成本任意、单位生产成本非增、容量非减。通过引入候选子计划概念，设计了一个O(T²)的动态规划算法。
In this paper, we study a class of the capacitated dynamic lot size problem, where, over time, the setup costs are nonincreasing, the unit holding costs have arbitrary pattern, the unit production costs are nonincreasing and the capacities are nondecreasing. We investigate the properties of the optimal solution for the problem and develop the concept of candidate subplan. It is proven that only the candidate subplans need to be examined in searching for an optimal solution. A dynamic programming algorithm, incorporating the concept of candidate subplan, is then devised which has run time complexity of O(T 2 ).