マルチプロセッサスケジューリング問題における先読みを考慮したヒューリスティックアルゴリズム

カテゴリ: 部門大会

論文No: GS18-3

グループ名: 【C】平成14年電気学会電子・情報・システム部門大会講演論文集

発行日: 2002/09/02

タイトル(英語): A Heuristic Algorithm Considering Look-Ahead for Multiprocessor Scheduling Problem

著者名: 齋藤 裕一(千葉工業大学),前川 仁孝(千葉工業大学),伊與田 光宏(千葉工業大学)

著者名(英語): Yuuichi Saitou(Chiba Institute of Technology),Yoshitaka Maekawa(Chiba Institute of Technology),Mituhiro Iyoda(Chiba Institute of Technology)

キーワード: マルチプロセッサスケジューリング問題|ヒューリスティックスケジューリングアルゴリズム先読み|先読み|分枝限定法|Multiprocessor Scheduling Problem|Heuristic Scheduling Algorithm|List Scheduling|Look-Ahead|Branch-and-Bound Method

要約(日本語): 実行時間最小マルチプロセッサスケジューリング問題は、

そのほとんどがNP困難となるため、

様々なヒューリスティックスケジューリングアルゴリズムが提案されてきた。

しかし、

そのような従来手法のほぼ全てはCP法に基づいていおり、

CP法のプライオリティが有効でない問題に対し最適解を得ることが難しい。

そこで、

本稿ではこのような状況の改善を目的としたアルゴリズムを提案する。

提案手法はリストスケジューリングの各割り当て時において、

先読みを利用し各タスクの優先順位を動的に変化させることにより、

静的な優先順位に従うと割り当て候補に選ばれないレディタスクを割り当て可能とする。

また、シミュレーションの結果を用い、

スケジュール長の精度、及び求解に要する処理時間の観点から提案手法の有効性を検証する。

PDFファイルサイズ: 4,095 Kバイト