Differential Evolution Algorithm Combined with Uncertainty Handling Techniques for Stochastic Reentrant Job Shop Scheduling Problem

Abstract

This paper considers two kinds of stochastic reentrant job shop scheduling problems (SRJSSP), i.e., the SRJSSP with the maximum tardiness criterion and the SRJSSP with the makespan criterion. Owing to the NP-complete complexity of the considered RJSSPs, an effective differential evolutionary algorithm (DEA) combined with two uncertainty handling techniques, namely, DEA_UHT, is proposed to address these problems. Firstly, to reasonably control the computation cost, the optimal computing budget allocation technique (OCBAT) is applied for allocating limited computation budgets to assure reliable evaluation and identification for excellent solutions or individuals, and the hypothesis test technique (HTT) is added to execute a statistical comparison to reduce some unnecessary repeated evaluation. Secondly, a reentrant-largest-order-value rule is designed to convert the DEA’s individual (i.e., a continuous vector) to the SRJSSP’s solution (i.e., an operation permutation). Thirdly, a conventional active decoding scheme for the job shop scheduling problem is extended to decode the solution for obtaining the criterion value. Fourthly, an Insert-based exploitation strategy and an Interchange-based exploration strategy are devised to enhance DEA’s exploitation ability and exploration ability, respectively. Finally, the test results and comparisons manifest the effectiveness and robustness of the proposed DEA_UHT.