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

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

基本信息

批准号：
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)正規および非正規目的関数間でのトレードオフを適度にバランスさせ得るように,遺伝子型-表現型変換部分を設計することが肝要であること,が指摘された.

今年，我们将设计多目标调度支持系统的总体配置功能，重点研究帕累托最优调度集的生成）构建方法，以及（b）多目标的应用和评估。从实际角度考虑正常和非正常目标函数的调度问题。具体来说，对于(a)，我们首先研究了使用遗传算法等进化计算算法的传统多目标优化框架方法，并总结了它们的特点，通过结合这些方法的优点，我们改进了帕累托最优解的生成方法。此外，对于(b)，我们解决了包含非正态目标函数的等效并行机多目标调度问题。我们考虑了如何通过设计一种将基因型转换为表型（时间表生成）的新程序来应用方法（a）。我们还实现了一个原型并评估了其有效性，使用该原型进行的计算机实验表明（a）可以直接获得。使用所提出的方法的各种帕累托最优调度； b）从支持多目标调度的角度来看，证实了提出帕累托最优调度集是有效的。此外，除了这些结果之外，作为生成和呈现更高质量调度的挑战，（c）指出设计基因型-表型转换部分非常重要，这样才能适当平衡正态和非正态目标函数之间的权衡。