A hybrid approach to the problem of task sequencing and tool changes with sequence-dependent set-up times

This study investigates the job sequencing and tool switching problem with sequence-dependent set-up times (SSP-SDST), in which it is necessary to determine the order of job processing, the loading of tools on the machine and the specific pairs of tools to be changed. The PT-SSP-SDST, an adaptation of the Parallel Tempering method, is proposed. The method models the tool switching subproblem as the linear assignment problem and applies a combination of the Hungarian algorithm and the keep tools needed soonest algorithm to its solution. Two variants of the proposed method were evaluated in benchmark instances of the literature. In comparison with two reference methods in the recent literature, the PT-SSP-SDST obtained the best solutions in all groups of instances evaluated, although with greater computational effort.