ジョブショップスケジューリング問題に対する局所探索法における新しい近傍設定法の提案

摘要

生産システムにおけるスケジューリング問題は従来から重要な問題の一つとして検討されてきた．代表的な問題として，1機械問題，並列機械問題，フローショップ問題，ジョブショップ問題がよく取り上げられ，その中でもジョブショップ問題は最適解を得皐ことが困難な問題として知られている．近年計算機の性能向上に伴って，多くの繰り返し計算を行なうことによって解を得る局所探索型アルゴリズムが注目され，ジョブショップ問題への適用例がよく報告されている．その代表的な解法として局所探索法，タブー探索法，模擬アニーリング法および遺伝アルゴリズムがある．いずれの解法においても，解の表現法や解近傍の設定方法がその解法の善し悪しを決定する．Genら，OnoらぉよびShiらは，同時期にジョブショップ問題に対してジョブあるいは作業を1列に並べた作業順列を用いる類似の解表現法を提案し，遺伝アルゴリズムを用いて精度の良い解を得たとの報告がある．一方，実際の生産現場では制限された時間内でスケジュールを決定する必要があり，多くの現場では，短時間に解を得るヒューリスティックルールに基づいた手法が用いられている．したがって，単に良い解を得るだけでなく，短時間で解を得る手法が必要とされている．タブー探索法，模擬アニーリング法および遺伝アルゴリズムは局所探索法を拡張した解法と見ることができ，局所探索法よりもわずかに良い解を得るために多くの時間を費す．したがって，短時間で解を得なければならない場合には，これらの手法は適していない．制限された時間を考慮して準最適解を求めるアルゴリズムとして，中野らは先の作業順列と同様の解表現を用いた局所探索法を提案した．この解法では，局所探索と大域探索の配分をうまく考慮し，またアクティブスケジュール法とセミアクティブスケジュール法の使い分けが行なわれている．しかし，作業順列には異なる順列が同一のスケジュールに対応するという冗長性が存在し，中野らのアルゴリズムでは作業順列を変更してもスケジュールが変わらない場合があり，探索の効率が悪い．