通信遅延を含むタスクスケジューリング問題の並列分枝限定法に基づく探索解法

DOI 機関リポジトリ Web Site

書誌事項

タイトル別名
  • ツウシン チエン オ フクム タスクスケジューリング モンダイ ノ ヘイレツ ブン シ ゲンテイホウ ニ モトズク タンサクカイホウ

この論文をさがす

抄録

type:Article

Since the task scheduling problems in the multiprocessor environments belong to the class of strong NP hard combinatorial optimization problem, the depth first search algorithms based on branch and bound(B&B) method are most effective to find an optimal solution. In order to reduce the search time with B&B method, it is the most important key to construct search algorithms with the way to bound many branches in the search space by more accurate lower bounds. However, it seems that there are no algorithms to create such lower bounds with consideration of processing system environments. In this paper, we propose three algorithms to create the lower bounds with consideration of number of processors, the lower bounds with consideration of processing time of successive tasks, and the lower bounds re-calculated in search process. Our experiments show that these algorithms give more accurate lower bounds and improve efficiency of search.

identifier:http://repository.seikei.ac.jp/dspace/handle/10928/362

収録刊行物

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ