A genetic algorithm to solve the general multi-level lot-sizing problem with time-varying costs

The multi-level lot-sizing (MLLS) problem in material requirements planning systems belongs to those problems that industry manufacturers daily face in organizing their overall production plans. However, this combinatorial optimization problem can be solved optimally in a reasonable CPU only when very small instances are considered. This legitimates the search for heuristic techniques that achieve a satisfactory balance between computational demands and cost effectiveness. In this paper, we propose a solution method that exploits the virtues and relative simplicity of genetic algorithms to address combinatorial problems. The MLLS problem that is examined here is the most general version in which the possibility of time-varying costs is allowed. We develop a binary encoding genetic algorithm and design five specific genetic operators to ensure that exploration takes place within the set of feasible solutions. An experimental framework is set up to test the efficiency of the proposed method, which turns out to rate high both in terms of cost effectiveness and execution speed.