Parallel Tempering Applied to Task Sequencing in Non-Identical Parallel Flexible Machines

The problem of task sequencing and tool changes on non-identical parallel machines is a variation of the classic problem of minimizing tool changes. In this context, different tasks require different sets of tools for their processing, and, as the machines do not hold all the tools simultaneously, interruptions are necessary for changeovers, which significantly impact the performance of the system. The problem, of NP-difficult nature, is treated considering the minimization of makespan. The application of the parallel tempering algorithm is proposed, whose results are evaluated in a comprehensive set of 640 benchmark instances extracted from the literature. The proposed method consistently outperformed the state-of-the-art approach, achieving all known optimal values and showing improvements of up to 14.19% over the best published solutions and a reduction of up to 98.45% in computational time. New best solutions were generated for 37.96% of the instances in the literature.