プレカット材料取り合わせのための新しい交叉操作による遺伝的アルゴリズム

摘要

So far, there are many researches on Bin Packing Problem (BPP). Cutting Stock Problem for timber precutting (CSP) is one of the kind of BPP. There are some solving methods such as Integer Programming method, First Fit method and Best Fit 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 plural lengths, which is different from general BPP. Therefore we devise doubled structure of gene. Reflecting dynamic change to crossover operation based on the result of combination, new model is built. Convergence process is improved largely by this newly proposed method.%プレカット材料取り合わせとは，いくつかの種類の長さrnの木材から住宅建築で要求される長さの部材製品を切り出rnす問題（Cutting Stock Problem: CSP）で，一次元のビンパッrnキング問題（Bin Packing Problem: BPP）として考えることrnができる。但し，通常BPPではビンの容量は一定とされるrnが，プレカットの場合は数種類の長さの材料を対象とする。