Single-point stochastic search algorithms for the multi-level lot-sizing problem

Among the most common decisions in manufacturing and distribution companies are probably those regarding Material Requirements Planning. However, that firms are daily confronted with these decisions does not mean that they are easy to handle. The multi-level lot-sizing (MLLS) problem is a combinatorial optimization problem which can only be solved optimally within reasonable delays when small instances are considered. This has motivated the search for heuristic techniques achieving a satisfactory balance between computational demands and cost effectiveness. In particular, the MLLS problem has characteristic features that have permitted the development of specific methods: interdependencies exist among stages in the product structure. In this paper, we examine the performance of single point stochastic techniques and compare them to several problem specific algorithms that exist in the literature. A large set of 280 variants of stochastic search algorithms is designed and applied to a variety of problems of small and large size. We find that these techniques, despite their simplicity and the widespread belief that they are generally efficient, only seldom outperform problem-specific algorithms, and when they do so it is usually associated with a much longer execution time. We also exhibit an efficient combination of search and annealing which is found able to produce significant and consistent improvements over problem-specific algorithms.