An Implementation of Parallel Tempering for the Sequencing Problem on Identical Parallel Machines with Tool Constraints

This study addresses the Task Sequencing Problem in Identical Parallel Machines with Tool Constraints, whose objective is to minimize the makespan considering setup time caused by tool changes. A parallel implementation of Parallel Tempering adapted to the problem is proposed by means of permutational coding, a decoding procedure for multiple machines, and an evaluation based on the greedy pipe construction algorithm. The parameters of the method were defined in preliminary experiments, and the approach was compared to the reference algorithm in the literature in benchmark instances. The results show that the method obtains new and better solutions in approximately 88% of the set of larger instances and reduces the makespan by up to 21.67% in relation to the reference method, indicating that Parallel Tempering is a competitive alternative for the problem addressed.