Development of Parallelized Solver for Task Scheduling Problems with Communication Delays : Improvements of Search Effectiveness using Optimal Scheduling of Sub-task-graphs

In order to implement high performance parallel processing, task scheduling is a very important key technology. However, task scheduling problems belong to very difficult optimizing problem and are not be able to solve in practical time. So, it is required to detect sub task graphs, which can be partially optimized independently, as soon as possible. Each sub task graph can be recognized as a macro task, therefore, total number of tasks will be reduced, and this results in reducing the time to solve scheduling problems. In this paper, we propose a new sub task graph detection mechanism which can find more sub task graphs. We show that some scheduling problems, which were impossible to solve by the conventional methods, can be solved