Heuristic search based on branch and bound method for task scheduling considering communication overhead

The task scheduling problems belong to the class of NP complete or strong NP complete combinatorial optimization problem. Taking account of communication overhead into task graphs makes these problems more difficult to solve by depth first search algorithm based on branch and bound method because the search space becomes much larger. In this paper, we propose an extended version of original priority levels used in Critical Path Method. The calculation of more accurate priority level of each task taking account of communication time among tasks requires by itself to solve another combinatorial optimization problem. So, our proposed new heuristic calculation method of each accurate priority level is completed in practically short time. By using our newly proposed priority level for both heuristics and bound operations in the search, it is shown that the scheduling time become shorter than the branch and bound search with the original priority level.