A genetic algorithm for the economic lot scheduling problem under the extended basic period and power-of-two policy

Abstract

The economic lot scheduling problem is a well-studied problem, which remains difficult to be solved optimally in its original form. The extended basic period and power-of-two policy restricts the solution choice but provides a good solution to the problem. However, this restricted problem is still NP-hard due to its combinatorial nature. In this paper, a genetic algorithm is investigated for solving the problem. The genetic algorithm uses an integer encoding scheme which encodes the basic period only implicitly. This lean representation cuts down the search space by one dimension which speeds up the search. In the evolution, both feasible and infeasible solutions are kept in the population, which works very well for high utilization problems. The experimental study shows that the designed algorithm is fast and efficient. It finds optimal solutions under the extended basic period and power-of-two policy for almost all the tested sample problems. © 2009 CIRP.