A fast branch-and-bound scheme for the multiprocessor scheduling problem with communication time

In this paper, we propose a fast branch-and-bound (B&B) algorithm for solving the multiprocessor scheduling problem with non-negligible communication time. The basic idea of our proposed method is to focus on an "inevitable" communication delay that could not be avoided in any assignment of tasks onto the processors. The proposed method is implemented as a part of B&B scheme, and the performance of the scheme is evaluated experimentally. The result of experiments implies that for randomly generated instances consisting of at most 300 tasks: 1) we could solve more than 90% of those instances within one minute if any communication takes zero time unit; 2) the percentage of hard instances increases by increasing the number of processors and the time required for each communication; and 3) the proposed method could achieve a significant improvement in increasing the lower bound of partial solutions especially for those hard instances. Those results suggest that the proposed method could output an optimum solution for many instances within a short computing time by combining it with a good heuristic to give a better upper bound.