進化型計算法に基づく多目的スケジューリング支援システムの開発

点击翻译按钮获取中文摘要

本年度は,多目的スケジューリング支援システムの全体構成について機能設計を行うとともに,特にパレート最適スケジュール集合の生成に焦点を当てて,(a)パレート最適スケジュール集合を直接的・効率的に生成する遺伝的アルゴリズム(GA)の構成法,および(b)現実的な観点から,正規および非正規目的関数を考慮した多目的スケジューリング問題に対する適用・評価,に関する研究・開発を行った.具体的には,(a)に関して,まず,GAなどの進化型計算アルゴリズムによる多目的最適化の枠組みについて,従来手法を調査するとともに,その特長を整理した.次に,これらの手法の長所を組み合わせる形で,GAに基づくパレート最適解集合の生成法を改良した.さらに,(b)に関しては,非正規目的関数を含む等価並列機械型多目的スケジューリング問題を対象として取り上げ,遺伝子型から表現型への変換(スケジュール生成)部の手続きを新たに設計する形で(a)の手法を適用する方法について検討した.また,プロトタイプを実現するとともに,その有効性および問題点について検討した.このプロトタイプを用いた計算機実験より,(a)提案手法によって,多様なパレート最適スケジュールを直接的に求めることが可能であること,(b)多目的スケジューリングを支援するという観点から,パレート最適スケジュール集合の提示が有効であること,が確認された.さらに,これらの結果に加え,より質の高いスケジュールを生成・提示するための課題として,(c)正規および非正規目的関数間でのトレードオフを適度にバランスさせ得るように,遺伝子型-表現型変換部分を設計することが肝要であること,が指摘された.