Research On Complex Shop Scheduling Problem Based On Intelligent Optimization Algorithm

Shop scheduling problems (SSPs) are usually complex problems which have features of NP-hard, nonlinear, strong constraints, multi-objective, uncertainty, and so on. Intelligent optimization algorithm is applied to solve complex SSPs has becoming a research hotspot in the academy and industrial field. Differential evolution(DE) algorithm is a new swarm-based intelligence evolutionary algorithm can be used to solve complex continuous or discrete optimization problems. Estimation of distribution algorithms (EDAs) are a class of novel stochastic optimization algorithms based on probability distribution models, can be used to solve the multi-variable related optimization problems effectively.In this paper, these two algorithms mentioned above will be applied to solve three kinds of important SSPs. The main work of this paper is summarized as follows:(1) A hybird differential evolution algorithm (HDE) is proposed for solving the multi-objective reentrant job-shop scheduling problem (MRJSSP) with total machine idleness and maximum tardiness criteria.(2) An adaptive hybrid estimation of distribution algorithm (AHEDA) is presented to minimize the weighted sum of average completion time and maximum tardiness for a certain kind of three-stage assembly flow shop scheduling problem with sequence-dependent setup times (TSAFSP_SDST). Firstly, the generation schemes of initial population and initial probability distribution model are proposed. Secondly, the adaptive update scheme based on information entropy is designed for probability distribution model, and the new population generation method is also constructed to keep excellent and good pattern. Thirdly, an Insert-based neighbor search is introduced to improve the local search ability.(3) A hybrid estimation of distribution algorithm (EDA) is proposed to optimize the makespan criterion for a certain kind of flexible assembly flow shop scheduling problem with different process (FAFSSP_DP). Firstly, a probability model update mechanism based on variable correlation is constructed. Meanwhile, the variable’s dependence corrections were studied; Secondly, the Insert-based neighbor search with first-improve-skip strategy is utilized to enhance the local search ability of HEDA.Simulation and experiment results demonstrate the effectiveness of the proposed algorithms, and the corresponding Shop scheduling simulation software were developed.