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.

Keywords:

• combinatorial optimisation
• genetic algorithms
• production planning
• sequencing
• minimisation of open stacks

Acknowledgements

This work was partially financed by the EU Commission, within the co-operative research project SCOOP (contract No. 032998) coordinated by Università Politecnica delle Marche, Ancona, Italy. The authors wish to thank Geoffrey Chu, Peter Stuckey, Alexandre Mendes and Alexandre Linhares for providing support in testing their algorithms.