Abstract
Our research aims to enhance a parallel Branch-and-Bound algorithm that has been developed by our research group for the Sequential Ordering Problem, as discussed in the previous work by Gonggiatgul et al. [1]. In this report, we worked on improving the existing pruning techniques such as history-based domination and thread stopping. The focus of the work is on enhancing the performance of the history-based domination technique to make it more space-efficient for better utilization of memory while still accelerating the Branch-and-Bound search. We have rewritten the current implementation of the history-based domination technique, which was using a single history table to keep all the previously visited subproblems. Theoretically, subproblems at shallower levels help us achieve more pruning. Therefore, we have implemented the history-based domination technique with multiple history tables, which allows us to eliminate deeper-level entries by deleting lower-level sub-tables and giving priority to shallower entries which resulted in improving memory utilization.