A Genetic Algorithm Applied to Cutting Stock Problem for Timber Precutting

So far, there are many researches on Bin Packing Problem (BPP). Cutting Stock Problem for timber precutting (CSP) is one of the kinds of BPP. There are some solving methods such as Linear Programming Relaxation method, First Fit method and Minimum Bin Slack method as for this. There are a few papers in which Genetic Algorithm (GA) is applied to BPP. This is because building model is difficult and generating effective individuals of next generation by crossover is also difficult. In this paper, an application of GA to CSP is examined. CSP contains mother materials consisted by several lengths in each grade, shape and species, which is different from general BPP. Therefore we devise double gene structure. Setting control parameter for crossover, an extended elitism method is newly devised. Elitism is extended for the same mother material species and elite group is protected and inherited. Thus, yield rate is improved largely and convergence speed is also improved by this newly proposed method