Complementary, competitive methods for multi-level lot sizing and scheduling: Tabu search and randomized regrets

This contribution presents two heuristic approaches for multi-level, single-machine lot sizing and scheduling. The first one is a variant of a so-called randomized regret based heuristic which is assumed to be the fastest available method for this particular class of problems. The second approach is a tabu search technique that is competitive with respect to both the run-time performance and the average deviation from the optimum objective function values. A computational study shows that these two methods are complementary, i.e. the randomized regret based heuristic performs good in those cases in which the tabu search gives poor results and vice versa. The combination of both thus provides a high performance approach to attack multilevel lot sizing and scheduling problems. It turns out that the average deviation from the optimum objective function value is round about 50% off from the stand-alone procedure results.