Application of Simulated Annealing and Genetic Algorithms in Solving Single Level Lot-Sizing Problems

Abstract

The single level lot-sizing problem arises whenever a manufacturing company wishes to translate an aggregate plan for production of an end item into a detailed planning of its production. Although this problem is widely studied in the literature, only laborious dynamic programming approaches are known to guarantee global minimum. Thus, stochastically-based heuristics that have the mechanism to escape from local minimum are needed. Two implementations of stochastic local search techniques for solving single level lot-sizing problems are proposed and the results of applying them to example problems are discussed. In the first implementation, simulated annealing is used to examine the neighborhoods of the replenishment points of an initial schedule obtained by following the standard Silver-Meal criterion. This provides a way of escaping local minimum in the total relevant costs per unit time for the current replenishment and thus improves the initial lot-sizing schedule. In the second implementation, a lot-sizing population-generating heuristic is used to feed chromosomes to a genetic algorithm which will try to find the optimal lot-sizing scheme without going through the process of examining the legality of the scheme for every generation. The application of the heuristic to generate an initial population results in a faster convergence in finding the optimal lot-sizing scheme. The result of this research shows that for uncapacitated lot-sizing problems using the sample of data, simulated annealing outperforms genetic algorithm in terms of run time and convergence rate. However, genetic algorithm outperforms simulated annealing in terms of a lower total production cost for problems with production penalties.