遺伝的アルゴリズムによるフレキシブルジョブショップスケジューリングの一手法

摘要

消費者ニーズの多様化に伴い，現代のものづくりは多品種少量生産，変種変量生産が主流となっている．その結果，製品毎に製造のための機械の使用順序が異なる，ジョブショップ生産に対するスケジューリング問題が活発に論じられている．この問題はNP（Non-deterministic polynomial time）困難であることが知られており，現実的な時間で解を得るために，メタヒューリスティクス，特に遺伝的アルゴリズム（Genetic Algorithm，GA）を用いた手法が多く提案されている．ジョブショップスケジューリングでは，各ジョブの各工程を処理する機械はあらかじめ指定されており，機械毎にどのジョブから割り付けるかというジョブ選択についての意思決定を行うことになる．しかし，現実のジョブショップ生産では，同じ機能を持つ機械（代替機械）が複数存在する場合が多い．代替機械の存在するジョブショップ生産，すなわちフレキシブルジョブショップ生産に対するスケジューリングでは，ジョブ選択に加えて，あるジョブをどの機械で処理するかという機械選択も行う必要がある．フレキシブルジョブショップスケジューリング問題をGAで解く手法として，GAと優先規則を融合した手法や，“Localization”と呼ばれる処理を初期個体に加える手法が提案されている．しかし，これらの手法では機械選択とジョブ選択とが2段階に分けられて行われており，解の探索範囲が狭まってしまう可能性が考えられる．