超大規模組合せ最適化問題に対する新解法の提案
設計、割り当て、スケジューリング等、様々な問題は組合せ最適化問題として定式化できる。しかし、実応用において厳密に最適な解を求めるのが不可能な場合も多い。そのような状況においても可能な限り良質な解を探索するために、これまでにも遺伝的アルゴリズムのような手法が提案されているが、万能ではない。本研究では、特に超大規模な組合せ最適化問題を対象とし、確率論、統計論的な観点から、最適と考えられる方法を追究している。
生産スケジュール改善サイクルは、ロット分割を段階的に進めることにより、段取り回数の増加を抑えつつ良好なスケジュールを得るための仕組みである。ロット分割は、生産スケジュール改善のための有効な手法の一つであるが、分割によってロット数が増えることになる。その結果として、総段取り時間が増加するだけではなく生産統制を複雑にしてしまう。このサイクルは四つのフェーズから構成され、受け入れ可能な生産スケジュールが得られるまで繰り返す。多目的最適化も可能である。
生産スケジュール改善サイクルの概念
スケジューリング問題を実用的に考えれば、最適なスケジュールではなく許容されるスケジュールを迅速に生成することが重要である。ロット分割を導入することで、許容できるスケジュールが得られやすくなる。しかし、ロット分割はロット数を増加させることになり、段取り時間の増加や生産統制を困難することが懸念される。そのため，最小限のロット分割に抑えることが不可欠である。
そこで，ロットをひとつ選定してはスケジューリングを実施し、許容可能なスケジュールに近づけていく方法が考えられる。右の図は生産スケジュール改善サイクルの概念である。この生産スケジュール改善サイクルは、ロット分割を段階的に進めることにより、段取り回数の増加を抑えつつ良好なスケジュールを得るための仕組みである。
生産スケジュール改善サイクルの各フェーズ
フェーズⅠ－分割ロットの選定
フェーズⅡ－スケジューリング
フェーズⅢ－段取り回数および段取り時間の軽減処理
フェーズⅣ－ガントチャートの確認
フェーズⅠでは、与えられたロットの中から一つを選択して二つに分割する。経過時間の短縮量は、分割されるロットによって異なる。そのため、分割数を抑えるには、フェーズⅠにおいてより短縮効果の大きいロットを選択する必要がある。効果的な選定手順として、CPT法を提案した。
フェーズⅡにおいては、段取り時間の影響を考慮に入れた高速なスケジューリング手法が不可欠である。そこで、GAを使ったスケジューリングを実施する。本研究では、nDSGAに段取り回数の軽減法を取り入れたアルゴリズムを開発した。染色体内に同種のロットを優先的に処理するかどうかを決める遺伝子を有している。
フェーズⅢでは、得られたスケジュールの評価尺度を悪化させない範囲で、同種のロットの連続処理を試みる。これにより、総段取り回数の軽減を図る。作業の前方移動処理と後方移動処理のアルゴリズムが組み込まれている。さらに、次の加工ロットの到着前に段取り替えを実施することで、総経過時間を短縮する。
最後に、フェーズⅣでガントチャートを表示させて確認する。目視によりスケジュールの修正を図る。任意のロットの加工順序をドラッグ・アンド・ドロップで変更することができる。この操作により染色体が変更され、結果は下部に表示され総経過時間も再計算される。順序変更の結果をもとのスケジュールと比較検討できる。
フェーズⅠ～Ⅲの性能評価(数値実験)
ロット選択法の評価
提案GAの有効性
段取りの削減効果
提案手法であるCPT法の性能と総加工時間最大ロットを選択するLTPT法とを比較した。問題数1000問題で数値実験をした結果、最良ロットと一致した問題数を上表の中央部にまとめた。CPT法は、おおよそ3%程度多く一致している。
表の右部は直接比較して、総経過時間の長短で比較した結果である。CPT法の方が優位性が示されている。
上のグラフは、ロット分割を進めたときの総経過時間と総段取り回数の変化をまとめたものである。左側の図は段取り時間10で、右側の図は段取り時間30のときである。
黒色のグラフは一般的なGAであり、赤色のグラフは提案GAである。提案GAは一般的なGAに比べて、段取り時間が小さいときに総段取り回数が大きくなり、段取り時間が大きいときには総段取り回数が小さくなっている。その結果として総経過時間は、提案アルゴリズムの方が優れている。
提案アルゴリズムは、段取り時間の大きさによって、段取り回数を柔軟に調整できていることがわかる。
段取り回数および段取り時間の軽減処理の効果を示したのが、上の図である。フェーズⅡで得られたスケジュールと比べて、総段取り回数が軽減と総経過時間の短縮が実現していることがわかる。
しかし、前者は分割数が増すにしたがって効果が大きくなるのに対し、後者は小さくなっていることがわかる。
生産スケジュールの多目的最適化
フェーズⅡにおいて、総経過時間と総納期遅れ時間の多目的最適化も可能である。総経過時間の大小によって世代交代する個体と総納期遅れ時間の大小によって世代交代する個体からGAにおける集団を構成する。どちら個体であるかは、下左図に示さりる通り染色体の属性部分を拡張して記録する。また、EDDルールやSLACKルールをスケジュール生成に組み込むことで総納期遅れ時間を効率よく最小化する。
そして、GAによる探索過程において生成されたすべてのスケジュールからパレート解を形成する。これにより、総経過時間と総納期遅れ時間のバランスの取れたスケジュールを選択することができる。下右図は、パレート解の一例である。分割が進むにつれてグラフが左下方向にシフトしていることが確認できる。
論文
「段取り時間を考慮した生産スケジュール改善サイクルの開発と数値実験」(2018)『日本経営システム学会誌』34(3)p.283-294.
「GAによる局所的な遅れのないスケジュール生成に基づくジョブ・ショップ・スケジューリング」(2015)『日本経営システム学会誌』31(1)p.1-11.
研究シーズ・教員に対しての問合せや相談事項はこちら
技術相談申込フォーム