DSpace About DSpace Software

SEIKEI University Repository >
01:紀要(Bulletin) >
11:理工学研究報告 >
第50巻第1号 >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10928/362

Title: 通信遅延を含むタスクスケジューリング問題の並列分枝限定法に基づく探索解法
Other Titles: A Parallelized Branch-and-Bound Search Method for Task Scheduling Problem with Consideration of Communication Overhead
Authors: 栗田, 浩一
甲斐, 宗徳
KURITA, Kohichi
KAI, Munenori
Keywords: Task scheduling
Combinatorial optimization problem
Branch and bound
Issue Date: Jun-2013
Publisher: 成蹊大学理工学部
Abstract: 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.
URI: http://hdl.handle.net/10928/362
Appears in Collections:第50巻第1号

Files in This Item:

File Description SizeFormat
rikougaku-50-1_17-27.pdf2.4 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback