Minimization of total flowtime in task sequencing and tool changes on non-identical parallel machines via Parallel Tempering

This study addresses the job sequencing and tool switching problem with non-identical parallel machines (SSP-NPM) under the objective of minimizing total flowtime (TFT). For this, the PT-NPM-TFT is proposed, a specialization of the Parallel Tempering (PT) framework to the problem treated, combining parallel execution of multiple replicas with algorithmic decisions oriented to TFT, including decoding strategy, evaluation by detailed plan of tool exchanges and neighborhoods compatible with the SSP-NPM solution space. The computational evaluation was conducted on the benchmark set of 640 instances in the literature, with direct comparison to the state-of-the-art method. The results show that the proposed approach is particularly effective in larger instances, obtaining improvements of up to 15.24% in TFT values, new better results in 68.75% of instances, and computational time reductions of up to 90.81%, with statistical superiority in the most difficult subset.