Combining Normal Approximation Heuristics With Simulated Annealing For The Stochastic Job-Shop Scheduling Problem

Abstract

This thesis addresses the Stochastic Job-Shop Scheduling Problem, incorporating uncertainty in the processing time. Efficiently creating robust schedules is computationally challenging due to the complex search space and stochastic variables. In this work, we adapt an approximation method previously used for Parallel Machine Scheduling, where normal approximation techniques are used as heuristic in a Simulated Annealing framework. By approximating the expected makespan, the algorithm significantly reduces the computational burden compared to traditional Monte Carlo simulations. We conducted a series of experiments on benchmark instances to evaluate the performance of the approximation method, assessing the percentiles of the resulting distribution together with the computation time. The results show that the method outperforms sampling-based methods in both solution quality and computational effort when there is much variability in the distributions and show comparable results with lower variability. This work advances heuristic scheduling methods by integrating probabilistic approximations into a metaheuristic framework, offering a scalable solution for large and uncertain scheduling environments.