ジョブショップスケジューリング問題へのスモールワールド理論の適用

摘要

ジョブショップスケジューリング問題(Job-shop Scheduling Problem, JSP)は多目的組み合わせ問題となり，一般に取り扱う問題が大きくなると数理的に解くのが殆ど困難な問題である．JSP の解法としては，経験的なルールを用いてスケジュールを作成するディスパッチング法，生物の進化を模倣した遺伝的アルゴリズム（Genetic Algorithm, GA）や生態のもつ免疫システムに基づく免疫アルゴリズム（Immune Algorithm, IA）等を用いてスケジュールを作成する方法が提案されている．本研究では，ジョブショップスケジューリング問題に筆者らが開発したジョブの多重遺伝子表現を用い，この遺伝子群をノードとしてDuncan J. Wattsのスモールワールド理論を適用する方法を提案し，レギュラーグラフとスモールワールから得られるスケジュールを数値計算実験により比較検証する．