A surrogate modelling approach combined with differential evolution for solving bottleneck stage scheduling problems

Surrogate modelling based optimization algorithms have been regarded as a powerful tool for solving expensive-to-evaluate functions, and numerous successful applications on optimization problems from various fields have been reported in literature. However, little effort has been devoted to solve complex combinatorial optimization problems through surrogate modelling, since evaluation for solutions of these problems is computationally cheap in general sense. In this paper, we firstly propose a two-layered decomposition of bottleneck stage scheduling problem, in which the subproblem of upper layer can be regarded as an expensive-to-evaluate problem, and the subproblem of lower layer is comparatively easy to solve. Then, we present a differential evolution algorithm combined with a surrogate model to solve the upper-layer subproblem, and the lower-layer subproblem is solved by an effective brand and bound algorithm. Considering that simulation data is generated in a continuous manner, we adopt an incremental extreme learning machine as the surrogate model to reduce the computational cost while preserving good generalization performance. Computational experiments demonstrate the effectiveness and efficiency of the proposed hybrid approach.