fdb – Forschungsdatenbank der Europa-Universität Viadrina Frankfurt (Oder)


Fanny Hein: Generating a decision rule for the capacitated lot sizing problem using Genetic Programming

VortagendeR Fanny Hein, Christian Almeder, Gonçalo Figueira, Bernardo Almada-Lobo
Tagung 11th International Workshop on Cutting, Packing and Related Topics
Ort Guimarães, Portugal
Jahr 2015


The dynamic lot sizing problem with limited production resources, better known as Capacitated Lot Sizing Problem (CLSP), is a standard optimization problem and one of the most critical in production planning. Since the CLSP is NP-hard, solution methods for large instances are mostly heuristic. Simple period-by-period approaches as proposed by Dixon and Silver (1981) and Maes and Van Wassenhove (1986) are widely-used in research and in practice due to the extremely low computational effort and their suitability for rolling planning horizons. These algorithms consist of three main steps: (i) products are ranked according to their estimated impact on the total cost; (ii) a feasibility check ensures that stocking up takes place if capacity limitations demand it; (iii) a decision is taken if a current production lot is extended or a new lot has to be set up.

The aim of this work is to apply genetic programming (GP) to automatically generate new decision rules for those heuristic algorithms for the CLSP. The GP-approach allows us to consider various problem-specific characteristics (such as cost ratios, capacity utilization, cumulative remaining demand or demand variability) leading to more complex rules that adapt to the problem environment. Preliminary tests show that we are able to obtain better solutions when using a GP-based priority rule for sorting the products, compared to the Dixon-Silver-criterion. Developing adaptive heuristics for the CLSP with uncertain demand is an interesting direction for future work.

Einordnung in die Universitätsstruktur