Heuristic genetic algorithms for general capacitated lot-sizing problems

The lot-sizing problems address the issue of determining the production lot-sizes of various items appearing in consecutive production stages over a given finite planning horizon. In general capacitated lot-sizing problems, the product structure can be a general acyclic network, the capacity constraints can be very sophisticated, and all the known parameters can be time-varying. This paper proposes heuristic genetic algorithms for these problems by designing a domain-specific encoding scheme for the lot-sizes and by providing a heuristic shifting procedure as the decoding schedule. The main contribution of these genetic algorithms is the presentation technique that encodes only the binary variables for the setup patterns but derives other decision variables by making use of the problem-specific knowledge. Some results from the computational experiments are also given.