Designing new heuristics for the capacitated lot sizing problem by genetic programming

Abstract This work addresses the well-known capacitated lot sizing problem (CLSP) which is proven to be an NP-hard optimization problem. Simple period-by-period heuristics are popular solution approaches due to the extremely low computational effort and their suitability for rolling planning horizons. The aim of this work is to apply genetic programming (GP) to automatically generate specialized heuristics specific to the instance class. Experiments show that we are able to obtain better solutions when using GP evolved lot sizing rules compared to state-of-the-art constructive heuristics.