A Hybrid Multi-chromosome Genetic Algorithm for the Cutting Stock Problem
Authors:
- Jin PengJPJin Peng
- Zhang Shu ChuZCZhang Shu Chu
- 1 November 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (21551456) , 508-511
Abstract
This paper presents a hybrid multi-chromosome genetic algorithm (HMCGA) to solve an in integer linear programming formulation of the Cutting Stock Problem (CSP). The CSP is an important class combinatorial problem. It is appropriate to minimize the raw material used by industries for fulfilling customer's demands. In such cases, classic models for solving the cutting stock problem are useless. HMCGA differ from previous application of genetic algorithm to CSP in that our coding contain tow chromosome, one represents the cutting pattern and another represents the frequencies of the cutting patterns in the first chromosome, rather than relying on a traditional genetic algorithm to decode each individual solution. Results obtained from computational experiments for ten benchmarks demonstrate that the performance of HMCGA is compared to that obtained using existing mete-heuristic algorithm.Keywords
This publication has 11 references indexed in Scilit:
- A genetic symbiotic algorithm applied to the one-dimensional cutting stock problemPesquisa Operacional, 2009
- An integrated cutting stock and sequencing problemEuropean Journal of Operational Research, 2007
- A coupling cutting stock-lot sizing problem in the paper industryAnnals of Operations Research, 2007
- Cutting stock waste reduction using genetic algorithms2006
- A genetic algorithm for bin packing and line balancing2003
- A new evolutionary approach to cutting stock problems with and without contiguityComputers & Operations Research, 2002
- LP models for bin packing and cutting stock problemsEuropean Journal of Operational Research, 2002
- Two-dimensional Cutting Stock with Multiple Stock SizesJournal of the Operational Research Society, 1991
- Lower bounds and reduction procedures for the bin packing problemDiscrete Applied Mathematics, 1990
- A typology of cutting and packing problemsEuropean Journal of Operational Research, 1990