A two-stage heuristic for the sequence-dependent job sequencing and tool switching problem

Abstract The job sequencing and tool switching problem is a combinatorial optimization problem that commonly happens in a flexible manufacturing system environment. In this type of environment, a set of flexible manufacturing machines can be configured with various tools to process different jobs and the requirement to switch tools may correspond to a reduction of productivity. Consequently, research on the job sequencing and tool switching problem has been concentrated on minimizing the number of tools switches. This paper discusses the sequence-dependent job sequencing and tool switching problem. The sequence-dependent job sequencing and tool switching problem extends the standard model by considering non-uniform setup times since industrial applications indicate that a tool setup time might be influenced by the previously installed tool at the same magazine slot. A two-stage heuristic procedure is developed here. In the first stage, an adaptive large neighborhood search is deployed for finding the near-optimal job sequence. Then, in the second stage, a combination of the Keep Tool Needed Soonest policy and simulated annealing is proposed for the tooling sub-problem. Comprehensive computational experiments are carried out to demonstrate the efficacy and robustness of the proposed method for solving the sequence-dependent job sequencing and tool switching problem.