A Simple Heuristic for Lot Sizing with Setup Times
针对带准备时间的单机批量问题，提出一个简单易懂且计算高效的启发式算法，能处理非平稳成本、需求和准备时间，并允许有限加班。实验表明，准备成本与持有成本之比、问题规模、产能约束紧度和需求波动是影响解质量的关键因素。
ABSTRACT This paper presents an easily understood and computationally efficient heuristic algorithm for the capacitated lot sizing problem (CLSP), the single machine lot‐sizing problem, with nonstationary costs, demands, and setup times. The algorithm solves problems with setup time or setup cost. A variation of the algorithm can solve problems when limited amounts of costly overtime are allowed. Results of experimentation indicate that the most significant effects on solution quality are due to the level of setup costs relative to holding costs and the size of the problems as determined by the number of items. Also affecting solution quality are tightness of the capacity constraint and variability of demand in a problem. When the capacity constraint is extremely tightly binding, it sometimes has difficulty finding solutions that do not require overtime.