A two-stage hybrid particle swarm optimization algorithm for the stochastic job shop scheduling problem

Real-world manufacturing systems are influenced by various random factors, which must be taken into consideration in order to obtain an effective schedule. However, compared with the extensive research on the deterministic model, the stochastic job shop scheduling problem (SJSSP) has not been sufficiently studied. In this paper, we propose a two-stage particle swarm optimization (PSO) algorithm for SJSSP with the objective of minimizing the expected total weighted tardiness. In the first-stage PSO, a performance estimate is used for quick evaluation of the solutions, and a local search procedure is embedded for accelerating the convergence to promising regions in the solution space. The second-stage PSO continues the search process, but applies a more accurate solution evaluation policy, i.e. the Monte Carlo simulation. In order to reduce the computational burden, the optimal computing budget allocation (OCBA) method is used in this stage. Finally, the computational results on different-scale test problems validate the effectiveness of the proposed approach.