An optimal model and a heuristic technique for multi-stage lot-sizing problems: Algorithms and performance tests

This paper is a study of optimal and heuristic lot-sizing problems for multi-stage production/inventory systems, with special emphasis on MRP-type manufacturing systems. Each stage has at most one immediate successor stage, but possibly a number of immediate predecessor stages. The case of one finished-product stage and deterministic demands over a finite discrete planning horizon are considered. A dynamic programming algorithm based on a pointer method, and a heuristic method are developed by applying the concepts of echelon stock and topology structure. The performance of the proposed heuristic is tested with 450 test problems in three kinds of comparison with the optimal solution algorithm. The results reveal that the proposed heuristic has an average percentage for cost error below 0.4, and computational savings are also achieved.