Computationally Efficient Optimal Solutions to the Lot-Sizing Problem in Multistage Assembly Systems
提出一种新的多阶段装配系统批量问题建模方法，利用“阶梯库存”概念和拉格朗日松弛法设计分支定界算法，在多达50个物料、15个阶段、18个时间周期的问题上验证了计算高效性。
The scheduling of lot sizes in multistage production environments is a fundamental problem in many Material Requirements Planning Systems. Many heuristics have been suggested for this problem with varying degrees of success. Research to date on obtaining optimal solutions has been limited to small problems. This paper presents a new formulation of the lot-sizing problem in multistage assembly systems which leads to an effective optimization algorithm for the problem. The problem is reformulated in terms of “echelon stock” which simplifies its decomposition by a Lagrangean relaxation method. A Branch and Bound algorithm which uses the bounds obtained by the relaxation was developed and tested. Computational results are reported on 120 randomly generated problems involving up to 50 items in 15 stages and up to 18 time periods in the planning horizon.