不均質な環境におけるマルチエージェントシステムのための公平かつ効率的なスケジューリングアルゴリズム

摘要

マルチエージェントシステムでは，クローンエージェントが並列に動作することで，ネットワーク上の複数のノードでの処理を効率よく遂行することが出来る．そのようなシステムにおいて，ユーザが指定した全てのノードにエージェントを送り，所望の処理を行わせる場合，最後のエージェントが処理を完了するまでの時間を短くすることが重要である．筆者らは，そのような場合において，処理の遅れているエージェントに着目した実行制御方式を提案しているが，ノードの処理能力や各エージェントのワークデマンドを均質と仮定しており，現実のモデルと乖離している．そこで本稿では，そのような不均質な環境におけるエージェントのスケジューリングアルゴリズムを提案する．本方式では，各ノードの処理能力と処理中のクローン数を考慮した上で，エージェントに均等なCPU時間を割り当てることにより，公平性を保証する．さらに，エージェントのワークデマンドから残り処理時間を予測することで，ワークデマンドの低いエージェントに優先的にCPU時間を割り当て，ワークデマンドに応じた応答時間を達成しつつ，全エージェントの平均応答時間の抑制を実現する．また性能評価を行い，提案方式の有効性を示す．