A Branch-and-Bound Algorithm for Solving the Multiprocessor Scheduling Problem with Improved Lower Bounding Techniques

摘要

In branch-and-bound (B&B) schemes for solving a minimization problem, a better lower bound could prune many meaningless branches which do not lead to an optimum solution. In this paper, we propose several techniques to refine the lower bound on the makespan in the multiprocessor scheduling problem (MSP). The key idea of our proposed method is to combine an efficient quadratic-time algorithm for calculating the Fernández''s bound, which is known as the best lower bounding technique proposed in the literature with two improvements based on the notions of binary search and recursion. The proposed method was implemented as a part of a B&B algorithm for solving MSP, and was evaluated experimentally. The result of experiments indicates that the proposed method certainly improves the performance of the underlying B&B scheme. In particular, we found that it improves solutions generated by conventional heuristic schemes for more than 20 percent of randomly generated instances, and for more than 80 percent of instances, it could provide a certification of optimality of the resulting solutions, even when the execution time of the B&B scheme is limited by one minute.