Efficient generation of high-quality initial solutions for the job sequencing and tool switching problem

Abstract

As an optimization problem, the job sequencing and tool switching problem has been the subject of several studies in operations research on its different variations, emphasizing its academic and industrial relevance. Although current methods approaching this problem yield extremely high-quality solutions, the computational time required has proven prohibitive when considering the practical aspects of the problem. Thus, in this paper, a method is presented for generating valid, high-quality solutions in low computational time, which can be used as initial solutions by more robust methods, aiming to accelerate them and contribute to the final quality of the solutions. The proposed approach consists of a new implementation of the random variable-neighborhood descent method using traditional and tailored local searches. Five traveling salesman problem heuristics were considered to generate the initial exploration point for the proposed method. The results obtained were compared with a recent strategy in the literature for generating initial solutions, which demonstrated significant improvement. Additionally, the proposed method was compared to the current state-of-the-art method for the addressed problem, and an average gap of only 5.36% was reported, evidencing the high quality of the solutions achieved for the proposed objective.