A Parallel Tempering Approach to the Problem of Job Sequencing and Tool Switching with Unsupervised Periods, Priorities, and Reentrancies

This study addresses the job sequencing and tool switching problem with unsupervised shifts, priorities and chains (SSP-USPrC), a variant of the job sequencing and tool switching problem motivated by a real industrial setting. The problem considers multiple identical parallel machines, priority jobs, reentrant jobs, and unsupervised production periods, aiming to maximize total profit over a finite planning horizon. To solve this problem, we propose an adaptation of the parallel tempering method, called PT-SSP-USPrC, in which the metaheuristic framework is specialized to represent, decode, evaluate, and generate solutions compatible with the operational constraints of the studied variant. Computational experiments, conducted on instances generated from real industrial data, compare the proposed method with a practitioner heuristic, a mathematical model, and a genetic algorithm from the literature. The results indicate that PT-SSP-USPrC produces higher-quality solutions and presents superior scalability.