Intelligent Algorithms Based On GA And EDA For Complex Job Shop Scheduling Problem

Flexible manufacturing system is an intricate artificial system, which features NP-hard, partial optimum, uncertainty, multi-objectives, multi-constrain and nonlinear. Production scheduling not only has gained extensive popularities in manufacturing system, but also become one of the toughest problems in theoretical researches. In the light of the application value and theoretical meaning, developing an intelligent optimization algorithm that is suitable for complex manufacturing shop scheduling problem has attracted an increasing attention in industrial and control fields. Genetic Algorithm (GA) is a kind of classical swarm intelligence optimization algorithm, which has been widely used in each filed. While, in recent years, Estimation of Distribution Algorithm (EDA), as a emerging intelligence optimization algorithm based on dominant individual probability distribution model, has got successful application in many industrial fields.Therefore, this paper mainly investigates the three kinds of crucial shop scheduling problems, which are based on solving algorithm of EDA or GA. The principle research is described as follow:(1)In view of the flow shop scheduling problem under the makespan criterion, a Genetic Algorithm with Insert neighborhood local search mechanism has been designed. It searches and finds optimum solution interval by GA. Through the simulation experiments on the different scale testing problems, it has proved the effectiveness and robustness of enhanced estimation of this algorithm.(2)In view of the no-wait job shop scheduling problem (NWJSSP) under the makespan criterion, an enhanced estimation of distribution algorithm(EEDA) has been redesigned by analyzing the structural features. This algorithm decodes the solution interval through time-schedule control, which could directly advance the solution quality based on work schedule decoding, accumulate information of optimum solution, and lead global research by processing the two-dimensional probability matrix into EDA probability model. All of these are conductive to participant of local research based on first-improve-skip with the local searching method based on Interchange neighborhood. Through the simulation experiments on several benchmarks and comparison with other algorithms, it has proved the effectiveness and robustness of enhanced estimation of distribution (EEDA).(3)In view of the re-entrant flow shop scheduling problem with sequence-dependent setup times, a Bayesian statistical inference-based estimation of distribution algorithm (BEDA) has been designed to resolve. In this algorithm, the solution quality based on work schedule decoding was enhanced by adopting active decoding. In addition, it describes the relationship between problem and variable quantity by processing simple the Bayesian statistical model into EDA probability model. Through learning and accumulating information of optimum solution, the algorithm research was guided. Through the simulation experiments on random generated testing data and comparison with other algorithms, it has proved the effectiveness and robustness of BEDA.