Abstract
The Sequential Ordering Problem (SOP) is a combinatorial optimization problem. Given a directed weighted graph and an unweighted directed graph representing precedence constraints among vertices, find a minimum-cost Hamiltonian path that satisfies the precedence constraints. Previous work on this problem included heuristic solutions and sequential optimal algorithms. To the best of our knowledge, there is no parallel optimal algorithm for the SOP. In this work, we propose a parallel optimal algorithm for the SOP using a branch-and-bound approach. Our current experimental results using 116 standard benchmark instances show that with a 2-hour time limit, the proposed parallel algorithm can solve 75 instances compared to 66 instances solved by the existing sequential algorithm. The average speedup across all solved instances is 2.05 for 4 threads. The best speedup with 4 threads is over 21.