Capacitated Lot Sizing with Setup Times
研究含准备时间的有限产能批量问题，用拉格朗日松弛分解为单产品子问题，通过次梯度优化和动态规划求解，再用启发式构造无加班可行方案。发现产能约束紧度是问题难度指标，且大问题反而更容易求解。
This research focuses on the effect of setup time on lot sizing. The setting is the Capacitated Lot Sizing Problem (the single-machine lot sizing problem) with nonstationary costs, demands, and setup times. A Lagrangian relaxation of the capacity constraints of CLSP allows it to be decomposed into a set of uncapacitated single product lot sizing problems. The Lagrangian dual costs are updated by subgradient optimization, and the single-item problems are solved by dynamic programming. A heuristic smoothing procedure constructs feasible solutions (production plans) which do not require overtime. The algorithm solves problems with setup time or setup cost. Problems with extremely tightly binding capacity constraints were much more difficult to solve than anticipated. Solutions without overtime could not always be found for them. The most significant results are that (1) the tightness of the capacity constraint is a good indicator of problem difficulty for problems with setup time; and (2) the algorithm solves larger problems better than smaller problems, although they are more time consuming to solve. This indicates that larger problems may be easier despite the greater computational effort they require.