A Dynamic Programming Approach for the Job Sequencing and Tool Switching Problem

Emma Legrand, Vianney Coppé, Daniele Catanzaro () and Pierre Schaus
Additional contact information
Daniele Catanzaro: Université catholique de Louvain, LIDAM/CORE, Belgium

No 2024030, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: 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. WeproposetheuseofA* anditsanytimevariantstoexplorethesolution 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.

Keywords: Combinatorial optimization; job sequencing; tool switching; brand and bound; A*; dynamic programming (search for similar items in EconPapers)
Pages: 16
Date: 2024-12-16
References: Add references at CitEc
Citations:

Downloads: (external link)
https://dial.uclouvain.be/pr/boreal/en/object/bore ... tastream/PDF_01/view (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2024030

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().