We present a new dynamic programming-based exact solution algorithm for the Job Sequencing and Tool Switching Problem (JS-TSP), a combinatorial optimization problem originating from manufacturing systems and encompassing the Traveling Salesman Problem as a special case. We propose a new family of lower bounds for the optimal solution to the problem, which are provably tighter than existing bounds in the literature and enhance both solution quality and pruning efficiency. We propose the use of A* and its anytime variants to explore the solution space of the problem as well as a specific data structure, called FreeTools, both to keep track of the state information and to compute incremental costs throughout the implicit search efficiently. Extensive computational experiments show that the presented approach brings significant performance improvements over state-of-the-art methods for the JS-TSP, including branch-and-bound and integer linear programming formulations.