抄録

◎澁谷知則・栗田浩一・甲斐宗徳（成蹊大）

タスクグラフで表現される並列処理対象を最小時間で処理するためには、タスクスケジューリングが重要である。しかし、タスクスケジューリングは強NP困難な最適化問題であり,現実的な時間で最適解を求めることは困難である。加えてプロセッサ間での通信遅延を考慮するよう拡張された問題ではさらに多くの求解時間を要することになる。本研究ではこのような問題に対して分枝限定法に基づく最適解探索を行う際、限定操作に使用する下限値に部分タスクグラフのスケジューリングを行うことによって通信遅延を考慮したより優良な下限値を求め、全体のタスクスケジューリングの並列探索解法の効率化を図った。