情報処理学会 第86回全国大会 会期:2024年3月15日~17日

5J-06
DF/IHS法の木構造を用いたタスクスケジューリング問題の下界値計算手法
○薬師啓太,中村あすか,前川仁孝(千葉工大)
本発表では, DF/IHS法を用いたタスクスケジューリング問題の最適解求解を高速化するため,下界値の計算を簡単化する手法を提案する.
DF/IHS法は分枝限定法に基づいて最も短いスケジュール長となるタスクの組合せを求める.
DF/IHS法の下界値計算はすべての未割当てタスクの実行に必要な時間を予測するため, 未割当てタスクが同じ部分問題に対して同じ計算を実行する場合があり, 計算に無駄が生じる.
そこで, 未割当てタスクが同じ部分問題をDF/IHSの木構造に基づいて検出し, 下界値の計算を簡単化することで, 探索の高速化が期待できる.