称号及び氏名

博士（経済学）豊田

学位授与の日付

平成２１年３月３１日

論文

名

丈輔

「Optimization for Combinatorial Problem of Timber Precutting」（住宅プレカットにおける組み合わせ最適化問題の研究）

論文審査委員

主査

竹安

数博

副査

石垣智徳

副査

森田裕之

論文要旨

多くの企業において最適化についての研究は、製造業における製造原価低減のための生産配分計画や部材調達計画、あるいは生産効率の高いマシンスケジューリングなどコストダウンや生産性向上に欠かせないテーマである。最適化問題の中で最も応用範囲の広いものの一つに組み合わせ問題がある。例えば典型的な組み合わせ問題である材料切り出し問題(Cutting Stock Problem: CSP)は、もともと材料の無駄を最小するような切り出す製品の組合せを考えるモデルであるが、ラインバランシングや積み込み問題などへの応用や、マイクロプロセサーのスケジューリングやメモリ配分などコンピュータシステムの分野、さらには投資計画や人的資源配分など経営分野への応用も考えられる。しかし現実には、実在の問題をモデル化して最適化を検討できるのは、専任技術者を擁する一部の企業であり、中小の多くの企業では、依然としてベテラン作業員の勘と経験による操業を行っているのが実態である。また本社部門でも、定型化／定例化できない企画業務をモデル化し最適化する例は少なく、潜在的損失は大きいと推定される。幅広く企業で適用されるためには、構造がシンプルでわかりやすく、容易にモデル化できるアルゴリズムが求められる。
一般に CSP は、あるいはその最も単純な BPP(Bin Packing Problem)でさえ NP 困難であり、多項式時間内に解くアルゴリズムは存在しない。従っていかに効率的に近似解を求めるかが課題となる。本論文では、中小規模工場の典型であるプレカット工場におけるプレカット部材の CSP を、複数の材料長を扱う一次元の Multiple Stock Length CSP としてモデル化し、実用性を念頭においたいくつかのアルゴリズムを、①処理の高速性、②アルゴリズム構造のシンプル性とわかりやすさ、③解の最適性、の 3 つの観点から検討し評価した。①はス-1-

ムーズなシステム導入や運用の最も基本的な条件である。②は広範囲に現実の問題をモデル化するためには必須の項目であり、③はヒューリステック解法の性能評価の基本である。
本論文では主に第３章と第４章で①と②を追求し、第５章と第６章で②と③を追求した。
第２章では準備として、ターゲットとする一次元 Multiple Stock Length CSP の定式化と、評価で共通に使用する典型的な木造住宅 10 邸分のプレカットデータの特性について述べ、プレカットのデータ構造は最適解が得られにくい「Hard 問題」に属することを示した。
第３章では、ビンの容量が一定の BPP の解法の１つである、簡単なロジックで高速に良好な結果が得られる First Fit (FF)法を使い、これを複数材長に対応するように改造した
Revised FF(RFF)法を検討した。FF 法は最初に見つけた空のあるビンにアイテムを入れるという単純なアルゴリズムであるが、我々は材料長を選択できるという利点を生かして、FF法を材料の側から見たアルゴリズムに組み替え、各長さの材料に割付けを試みて最も歩留の良い材料と割付け製品群を順次確定していく方法とした。しかしこの方法の弱点は、良い「材料－製品群」を先取りしていくため、最後の割付けで歩留が落ちることである。これを緩和するため、残りの製品を割付けるのに必要な材料が予測できる段階になったら、「材料－製品群」の選択基準を“歩留最大”から“使用材料最小”に切り替える方式を組み込み、これを Revised FF(RFF)法とした。これをベースに、先の弱点の別の最も簡単な対応手段である、製品の長さ順処理と最長製品は必ず割付けるという条件をつけた RFF
Decreasing (RFFD)法、製品の処理順をランダムに変化させて RFF を繰り返し実行し、最も良い結果を採用する RFF Randomizing(RFFR)法、さらに RFFD の高速性を生かして、選択時に RFFD で最終歩留を予測しながら「材料－製品群」を選択する Recursive RFFD(R-RFFD)法の３つのアルゴリズムを提案した。これらをプレカット CSP に適用した結果、一般に 90%以下と言われている歩留を、3 秒以内で 92%～95%の値を得ることができた(RFFR の試行回数は製品数×材料長種数で設定)。
第４章では、一般に FFD よりも良い結果が得られるといわれている Minimum BinSlack(MBS)法に注目し、第３章の各アルゴリズムのベースとなっている FFD を MBS で置き換えられないかを検討した。MBS は総当りでビンの空きが最も少なくなるアイテムの組み合わせを検索し、ビンを順番に満たしていく方法で、ビン（材料）視点のアルゴリズムであり、最も良い組み合わせを先取りするため FFD よりさらに「最後のビンの空きが大きくなる」傾向をもつ。従って、第３章の弱点克服のための考え方をそのまま当てはめることができる。但し、MBS の場合は総当りで製品の組み合わせを検索するため、問題によっては指数的に処理時間が増加する危険があり、特に繰返し試行する R-RFFD では、FFD を MBSに置き換えると膨大な処理時間となることも予想される。そこでまず MBS の高速化を検討した。MBS のロジックの動きを注意深くチェックし無意味な検索をカットすることで、検索回数をグプタ(Gupta)の提案したオリジナルアルゴリズムの 1/1000 に、フレツァー(Fleszar)の提案した改造アルゴリズムの 1/40 にまで減らすことに成功した。そしてこの高速 MBS をFFD の代わりに利用することで、RMBS および R-RMBS アルゴリズムを組み立てた。これ-2-をプレカットに適用し、RFFD および R-RFFD とほぼ同じ処理時間で、全般にさらに良い結果を得た。
FF および MBS を利用したアルゴリズムの最大の特徴は、先の条件①と②を完全に満たす点で、プレカットではいずれも邸あたり２秒以内で公開特許の方法を上回る 92%以上の割付けを実現している。この処理速度であれば、例えばこれらのアルゴリズムを組み合わせて適用して最も良い結果を採用するという、簡単な歩留向上策も可能である。
第５章では、解の最適性をテーマに遺伝的アルゴリズム(Genetic Algorithm: GA)の適用検討を行った。CSP タイプの組み合わせ問題に対する GA 適用についての過去の研究は、製品の並びを遺伝子とする Order-Based モデルと「材料－製品群」を遺伝子とする Group-Basedモデルの２つに分類できる。前者はモデルとしてはわかりやすいが、“製品順”という本来不要の要素が持ち込まれるため冗長度が高く、また順序の微細な変化が製品群全体の再編成を招くため収束性が極めて悪いことが指摘されている。後者はフォークナー(Falkenauer,)が収束性の良いモデルを提案しているが、染色体が可変長となるため特殊で複雑な交叉操作を工夫する必要がある。また Order-Based モデルでも、順序を扱うため巡回セールスマン問題で使われる特殊な交叉操作が必要である。
本論文では敢えて収束性の悪い Order-Based モデルを基本に、さらに並び順をソートキー表現することで交叉に順序の乱れを持ち込まないモデルとし、収束性を確保するため「材料歩留の高い材料－製品群は次世代に引き継がれやすい傾向がある」ような交叉制御を工夫した。遺伝子構造は、順序ソートキーとなる遺伝子 GeneP と材料長を指定する GeneBの２重構造とし、GeneP を材料残材率と群を識別する調整項で構成することで、同一群内に順序を持ち込まないと同時に、材料歩留の高い製品を早く割付けて他の割付けの影響を少なくする。一方、残材率の関数で表される交叉制御関数を定義し、この関数を交叉確率にして材料歩留の高い親の遺伝子が子に渡る確率が高くなるような制御を行う。この交差方式を、遺伝子レベルで子に渡す遺伝子の選択を行うことから「拡張エリート選択法(Extended Elitism Method: EEM)」と名付けた。EEM を組み込んだこのモデルをプレカット適用し、高い歩留を得るとともに、一般の一様交叉と比較して圧倒的に収束性が高いことを確認した。
EEM は高い収束性を示すが、優秀な遺伝子を片親だけから引き継ぐという特性がある。
そこで第６章では、両親からそれぞれ優秀な遺伝子を引き継ぐ交叉ルールを検討した。遺伝子は EEM と同じ構造とし、遺伝子レベルの適応率を材料歩留で定義して、この適応率を親同士で比較することで引き継ぐ遺伝子を決定する「対戦交叉法(Tournament Crossover
Operation Method: TCOM)」を提案した。さらに多様性を維持するため、歩留が低い個体は温度が高くなるような個体の温度を定義し、交叉制御に両親の温度差をパラメータとした「焼きなまし法」を取り入れた。温度差が大きい場合は、温度の高い親の遺伝子はたとえ遺伝子の適応率は高くても、子に伝わらない場合もありうるような確率制御を行う。このモデルをベンチマークデータで評価し、EEM より良い結果が得られることと、焼きなまし-3-法が多様性維持に有効であることを確認した。
GA は結果が確率的に変動し、処理時間を長くすればより良い結果が得られる確率が高くなる。プレカット CSP では、数秒で結果の出る FFD や MBS ベースのアルゴリズムに比べ GA は数十分単位の時間がかかった。しかしプレカットでの実用を考えると長くても数分が処理時間の目処と考える。そこで最適解のわかっている邸を基準に解の分布を分析し、繰返し回数や世代数の調整によって、数分以内に数十分の処理結果と同じ解が得られることを確認した。
本論文で提案したアルゴリズムは、手軽にいろいろな問題に適用できる実用性を最大の目的として検討したものである。今回はプレカット CSP を例として検討したが、CSP のみならず生産現場のいろいろな最適化問題や、本社部門も含めたいろいろな企業活動の場における、組み合わせ問題に適用されることを期待したい。

-4-