A hybrid differential evolution algorithm for job shop scheduling problems with expected total tardiness criterion

In real-world manufacturing systems, the processing of jobs is frequently affected by various unpredictable events. However, compared with the extensive research for the deterministic model, study on the random factors in job shop scheduling has not received sufficient attention. In this paper, we propose a hybrid differential evolution (DE) algorithm for the job shop scheduling problem with random processing times under the objective of minimizing the expected total tardiness (a measure for service quality). First, we propose a performance estimate for roughly comparing the quality of candidate solutions. Then, a parameter perturbation algorithm is applied as a local search module for accelerating the convergence of DE. Finally, the K-armed bandit model is utilized for reducing the computational burden in the exact evaluation of solutions based on simulation. The computational results on different-scale test problems validate the effectiveness and efficiency of the proposed approach.

Figure optionsDownload as PowerPoint slideHighlights
► The job shop scheduling problem with stochastic processing times and total tardiness objective is studied.
► A hybrid differential evolution (DE) algorithm is proposed to solve the problem.
► A parameter perturbation algorithm is applied as a local search module to accelerate the convergence of DE.
► The K-armed bandit model is utilized to control the computational burden in the simulation-based evaluation of solutions.
► The effectiveness of the proposed approach is verified by extensive computational results on different-scale test problems.