Solution Of Complex Shop Scheduling Problem Based On DE And EDA 's Intelligent Algorithm

Shop scheduling problem, there are some complex features such as nonlinear, strong constraints, multi-objective, uncertainty, and so on. Such problems also have a characteristic of large-scale which usually results in modeling difficulty. Developing effective intelligent optimization algorithm for complex shop scheduling problem has become a hot research topic of the production scheduling field. Differential evolution (DE) is a new swarm-based intelligence evolutionary algorithm can be used to solve complex optimization problems. Estimation of distribution algorithm (EDA) is an evolutionary algorithm based on probabilistic models of the excellent individuals, and searching for the solution space from a macro perspective will be realized.In this paper, these two algorithms mentioned above will be applied to solve complex shop scheduling problem. The main work can be elaborated in following three aspects.(1) A hybrid differential evolution algorithm (HDE) is developed for solving the no-wait flow shop scheduling problem (NFSSP) with sequence-dependent setup times (SDSTs) and release dates (RDs). The objective function to be minimized is total tardiness.(2) Aiming at m-machine reentrant permutation flow-shop scheduling problem (MRPFSSP), three kinds of algorithms based on EDA are proposed. Firstly, a hybrid estimation of distribution algorithm (HEDA) based on the structure of the problem is proposed. Secondly, a hybrid self-adaptive EDA-based algorithm(SHEDA) is presented, and a self-adaptive adjusting strategy is embedded into EDA reasonably, and the learning rate could be adjusted automatically. Thirdly, a copula-based hybrid estimation of distribution algorithm(CHEDA) is developed, and a critical-path-based local search strategy is designed to enhanced the exploitation ability of CHEDA. Meanwhile, the variable’s dependence corrections (not only the correlations) were studied.(3) Focusing on parallel machine scheduling problem (PMSP), some certain kinds of EDA-based algorithms are proposed, and the optimization objective is makespan. Firstly, an adaptive estimation of distribution algorithm, namely AEDA. is proposed to solve the identical parallel machine batch scheduling problem. Secondly, a novel estimation of distribution algorithm(NEDA) is proposed for a certain kind of complex heterogeneous parallel machine scheduling problem, i.e.. the heterogeneous parallel machine scheduling problem with job processing constraints and sequence-dependent setup times (HPMSP_JPCSST). Thirdly, a genetic algorithm-estimation of distribution algorithm (GA-EDA) is proposed to optimize a certain kind of heterogeneous parallel machine scheduling problem, i.e., the heterogeneous parallel machine scheduling problem with multiple operations and sequence-dependent setuptimes (HPMSP_MOSST). Lastly, a Copula-theory-based multi-objective estimation of distribution algorithm, namely CMEDA, is presented to deal with multi-objective HPMSP_MOSST, and the criterias to be optimized are makespan and the total changerover cost (TCC).Simulation experiments and algorithm comparisons demonstrate the effectiveness and robustness of the proposed algorithms.