Simulation-based matheuristic for job sequencing and tool switching on non-identical parallel machines under uncertainty

This paper investigates the job sequencing and tool switching problem with non-identical parallel machines and stochastic processing times (SSP-NPM-SPT). The objective is to jointly determine the job processing sequence and the tool switching schedule while managing the uncertainty in the processing times, to minimize the makespan. To tackle this challenging problem, a simulation-based matheuristic approach was adopted. Specifically, a Monte Carlo simulation was used to handle uncertainty by considering multiple scenarios, the mean value problem was used to aggregate these scenarios and derive reliable lower bounds, and a data-driven approach was adopted to account for variability in the scenarios. Computational experiments were conducted on adapted benchmark instances from the literature to evaluate different scenario generation strategies and aggregation methods. The results show that the optimal configurations involve variability rates of 0.1 for the Normal and Log Normal distributions, and 0.2 for the Gamma distribution. They also involve scenario counts equal to twice the number of jobs, and scenario groupings equal to one-fifth of the number of jobs. These settings significantly improve accuracy and computational efficiency.