An adaptive genetic algorithm for large-size open stack problems

Abstract

The problem of minimising the maximum number of open stacks arises in many contexts (production planning, cutting environments, very-large-scale-integration circuit design, etc.) and consists of finding a sequence of tasks (products, cutting patterns, circuit gates, etc.) that determines an efficient utilisation of resources (stacks). We propose a genetic approach that combines classical genetic operators (selection, order crossover and pairwise interchange mutation) with an adaptive search strategy, where intensification and diversification phases are obtained by neighbourhood search and by a composite and dynamic fitness function that suitably modifies the search landscape. Computational tests on random and real-world benchmarks show that the proposed approach is competitive with the state of the art for large-size problems, providing better results for some classes of instances.