進化型計算アルゴリズムに基づく適応的スケジューリング・システムの開発

本年度は,問題に含まれるパラメータが予めわかっている場合だけでなく,動的に変化する場合あるいは不確定な場合の(すなわち,ダイナミック性・リアルタイム性が要求される)スケジューリング問題を対象とし,解(スケジュール)そのものでなく,これを生成するルール(スケジューリング・ルール)を問題の解表現としたスケジューリング・システムの枠組みを構築するとともに,(a)スケジューリング・ルールの整理とその表現方法の決定,(b)スケジューリング・ルールの評価手法の実現,に関する研究を行った.具体的には,(a)に関して,従来のルールベース・スケジューリングにおけるディスパッチング規則の荷重和をとって優先的に割り付けられる作業を決めるものとし,このときの重み係数を後件部に持つルール(if-then型ルール)を考えた,なお,このルールの前件部には,スケジューリングの過程における状態を持たせた.さらに,(b)に関しては,一連のルールを適用した際に生成されるスケジュールの評価を個々のルールに還元することが必要であり,強化学習アルゴリズムの一つである遺伝的アルゴリズムに基づく学習方式(ピッツバーグ・アプローチおよびミシガン・アプローチ)を採用した.このスケジューリング・ルール評価システムのプロトタイプを計算機上に作成し,まず(a)について,ピッツバーグ・アプローチを用いた計算機実験より,・適用されるルールをスケジューリングの途中で動的に切り替えることによって,より有効なスケジューリングが可能となること,が確認された.次に(b)について,ミシガン・アプローチに基づいてスケジューリング・ルールを評価する方法を実現するとともに,種々の計算機実験を行った.これより,・現時点においては,あらゆる状況下で個々のスケジューリング・ルールを正当に評価できるシステムの完成には到っていないが,そこでの問題点および課題が具体化された,という結果を得た.

本年度は,問題に含まれるパラメータが予めわかっている場合だけでなく,動的に変化する場合あるいは不確定な場合の(すなわち,ダイナミック性・リアルタイム性が要求される)スケジューリング問題を対象とし,解(スケジュール)そのものでなく,これを生成するルール(スケジューリング・ルール)を問題の解表現としたスケジューリング・システムの枠組みを構築するとともに,(a)スケジューリング・ルールの整理とその表現方法の決定,(b)スケジューリング・ルールの評価手法の実現,に関する研究を行った.具体的には,(a)に関して,従来のルールベース・スケジューリングにおけるディスパッチング規則の荷重和をとって優先的に割り付けられる作業を決めるものとし,このときの重み係数を後件部に持つルール(if-then型ルール)を考えた,なお,このルールの前件部には,スケジューリングの過程における状態を持たせた.さらに,(b)に関しては,一連のルールを適用した際に生成されるスケジュールの評価を個々のルールに還元することが必要であり,強化学習アルゴリズムの一つである遺伝的アルゴリズムに基づく学習方式(ピッツバーグ・アプローチおよびミシガン・アプローチ)を採用した.このスケジューリング・ルール評価システムのプロトタイプを計算機上に作成し,まず(a)について,ピッツバーグ・アプローチを用いた計算機実験より,・適用されるルールをスケジューリングの途中で動的に切り替えることによって,より有効なスケジューリングが可能となること,が確認された.次に(b)について,ミシガン・アプローチに基づいてスケジューリング・ルールを評価する方法を実現するとともに,種々の計算機実験を行った.これより,・現時点においては,あらゆる状況下で個々のスケジューリング・ルールを正当に評価できるシステムの完成には到っていないが,そこでの問題点および課題が具体化された,という結果を得た.