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

基于进化计算方法的多用途调度支持系统开发

基本信息

批准号：
08750481
负责人：
玉置久
金额：
$ 0.64万
依托单位：
Kobe University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1996
资助国家：
日本
起止时间：
1996 至无数据
项目状态：
已结题

项目摘要

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

今年，我们设计了多目标调度支持系统的整体结构，并专注于帕累托最佳时间表集的产生，并在（a）构建遗传算法（GA）（a）直接有效地生成帕累托最佳时间表集的遗传算法（GA）的构建，以及（b）对多个目标的应用和估计，不合时宜地构成了一个正常的问题和估计 - 不合时宜地涉及一个正常的计划。具体而言，关于（a），我们首先使用进化计算算法（例如GA）研究了多目标优化框架的常规方法，并组织了这些特征。接下来，我们通过组合这些方法的优点来改进基于GA生成帕累托最佳解决方案集的方法。此外，关于（b），我们讨论了包括非规范目标函数的等效平行机械多目标调度问题。我们讨论了将方法（a）应用于基因型到表型转换过程（计划生成）部分的新设计的方法。我们还实施了原型，并检查了其有效性和问题。从使用该原型的计算机实验，可以通过提出的方法直接确定（a）可以直接确定各种帕特托 - 最佳的时间表，并且（b）从支持多目标计划的角度出现帕特托最佳时间表。此外，除了这些结果外，还指出（c）设计基因型 - 表型转换零件很重要，以使正常目标和非正常目标函数之间的权衡可以适度平衡。