A hybrid differential evolution approach based on surrogate modelling for scheduling bottleneck stages

Surrogate modelling based optimization has attracted much attention due to its ability of solving expensive-to-evaluate optimization problems, and a large majority of successful applications from various fields have been reported in literature. However, little effort has been devoted to solve scheduling problems through surrogate modelling, since evaluation for a given complete schedule of these complex problems is computationally cheap in most cases. In this paper, we develop a hybrid approach for solving the bottleneck stage scheduling problem (BSP) using the surrogate modelling technique. In our approach, we firstly transform the original problem into an expensive-to-evaluate optimization problem by cutting the original schedule into two partial schedules using decomposition, then a surrogate model is introduced to, quickly but crudely, evaluate a given partial schedule. Based on the surrogate model, we propose a differential evolution (DE) algorithm for solving BSPs in which a novel mechanism is developed to efficiently utilize the advantage of the surrogate model to enhance the performance of DE. Also, an improved adaptive proximity-based method is introduced to balance the exploration and exploitation during the evolutionary process of DE. Considering that data for training the surrogate model is generated at different iteration of DE, we adopt an incremental extreme learning machine as the surrogate model to reduce the computational cost while preserving good generalization performance. Extensive computational experiments demonstrate that significant improvements have been obtained by the proposed surrogate-modelling based approach.