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

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.