並列計算を利用した大規模スケジューリング問題の高速解法に関する研究

Abstract

本論文は、大規模なスケジューリング問題に並列計算を導入することによって、実用に耐えうる準最適解を高速に導出しようとするものである。スケジューリング問題はNP(Non-deterministic Polynomial)困難問題の代表格として知られており、現在でもオペレーションズリサーチや計算量理論、人工知能といった分野において盛んに研究が行われている。スケジューリング問題を始めとするNP困難問題は問題のサイズとともに探索空間が組み合わせ爆発を起こすために、真の最適解を導出することは特殊な場合を除いて不可能である。そのため、近年では真の最適解の代わりに「最適にできるだけ近い解」を「実用的な時間範囲内で求める」ことが要請されるようになっている。これを実現することは、実際に大規模スケジューリング問題を日々解かなければならない部品組立工場などの要望に沿うことにもなる。しかしこういった現場では、ある機械に複数のジョブが到着した場合のコンフリクト解消手法として、事前に恣意的に定めた優先規則に基づいて投入ジョブを決定するリアクティブな手法が広く採用されているのが現状である。この手法は取り扱いは容易であるが、必ずしもよいスケジュールを生成できない。そこで本研究では、スケジュール生成の際に最適性を陽に扱うことのできる高速準最適解導出手法として、ラグランジュ分解調整法を利用する。本手法は比較的高速で準最適解を得られるメリットと同時に解の品質評価性能をも有し、すでに1部の生産スケジューリング問題に適用され、その効果が確認されている。本研究ではこの解法の構造的な特徴に着目し、並列計算を導入して計算時間を大幅に短縮し、相当大規模な問題でも十分実用的な時間内に計算を完了し、最適に近い解を出力することを目的としている。本論文では、ラグランジュ分解調整法の構造的な特徴や適用のための制限などを明らかにした上で、生産スケジューリング問題以外の新しいアプリケーションとして、(1)宇宙ステーションにおける宇宙飛行士の作業内容を決定する「ステーション問題」、(2)大学による小型衛星の運用効率向上を目指した地上局ネットワークにおいて、いつ、どの衛星が、どの地上局を利用して運用を行うのかを決定する「地上局ネットワーク問題」を提案し、その効果を確認する。その上で、ラグランジュ分解調整法に並列計算を導入する方法を示し、高速化のためにはどのような処理の工夫が必要かを論じる。また、実際に並列計算を導入した場合にどの程度の計算処理の高速化が図れるかを推算する。並列化の実現手法としては特に専用計算機を採用し、専用回路に高い並列度で計算させることによる高速化をねらう。また専用計算機を利用することによって、超高速な準最適解導出手法が低コストに構築できることを示す。以上の成果は、本論文で示したスケジューリング問題のみならず、特定の条件を満たす広い範囲の数理計画問題に対して適用でき、それらを必要とする現場への導入も比較的容易と思われることから、新しいスケジューリングツール、最適化ツールとしての普及が期待される。