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

DOI IR Web Site

Bibliographic Information

Other Title
  • ツウシン チエン オ フクム タスクスケジューリング モンダイ ノ ヘイレツ ブン シ ゲンテイホウ ニ モトズク タンサクカイホウ
  • A Parallelized Branch-and-Bound Search Method for Task Scheduling Problem with Consideration of Communication Overhead

Search this article

Abstract

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

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top