Randomized multi-level lot-sizing heuristics for general product structures

We consider the multi-level lot-sizing (MLLS) problem as it occurs in material requirements planning systems, with no capacity constraints and a time-invariant cost structure. Many heuristics have been developed for this problem, as well as optimal solution methods which are applicable only to small instances. Few heuristic approaches however have been specifically built to address the MLLS problem with general product structures of large size. In this paper we develop randomized versions of the popular Wagner–Whitin algorithm [Management Science 5 (1958) 89] and the Silver–Meal technique [Production and Inventory Management 14 (1973) 64] which can easily handle product structures with numerous common parts. We also provide randomized variants of more sophisticated MLLS heuristics such as Graves’ multi-pass method [TIMS Studies in the Management Sciences 16 (1981) 95], a technique due to Bookbinder and Koch [Journal of Operations Management 9 (1990) 7] and that of Heinrich and Schneeweiss [Multi-Stage Production Planning and Control, Lecture Notes in Economics and Mathematical Systems, Springer, 1986, p. 150]. The resultant heuristics are based on original randomized set-up cost modifications designed to account for interdependencies among stages. The effectiveness of the proposed algorithms is tested through a series of simulation experiments reproducing common industrial settings (product structures of large size with various degrees of complexity over long horizons). It is concluded that the randomized version of the Graves algorithm outperforms existing heuristics in most situations. The randomization of the Wagner–Whitin algorithm proved to be the best single-pass method while only requiring a low computational effort.