抄録
RA-006
通信を考慮したタスクスケジューリング問題の効率的な並列探索解法の提案
◎栗田浩一・宇都宮雅彦・塩田隆二・甲斐宗徳（成蹊大）
強NP困難な組み合わせ最適化問題であるタスクスケジューリング問題を，実際のマルチプロセッサモデルに適用する場合，タスクの依存関係により生じるプロセッサ間の通信時間を考慮したスケジューリングが必要となる．本論文では，通信を考慮したスケジューリング問題の探索時間の削減に有効となる枝切り操作の効率化と探索の並列化について，新たなヒューリスティックスとして「通信を考慮したタスク下限値の導出法」，および「探索の並列化効率を向上させる探索枝生成順序操作」を提案する．これらの提案アルゴリズムを用いて従来の探索手順に通信を考慮した修正を加えることにより，解の探索効率を向上させることが可能となった．