Hybrid Differential Evolution Algorithm Based On Complex Zero Wait Pipeline Scheduling Problem And Job Shop Scheduling Problem

Production scheduling problems (PSPs) are often of some complexities, such as NP-hard, large-scale, and strong constraint. The study on the effective algorithms of PSPs has gained more and more attention from both industry and academia. As a simply and effective intelligent algorithm, differential evolution (DE) has attracted much attention and gained successful applications in a variety of fields. Thus, this dissertation aims at studying scheduling algorithms based on hybrid DE for three kinds of important PSPs. The main work of this dissertation is summarized as follows:Firstly, after analyzing the structural properties of the no-wait flow-shop scheduling problems with sequence-dependent setup times and release dates under the total completion time criterion, we design an effective local search based on speed-up solution evaluation method and reasonably fusing it with DE to propose a hybrid DE. Simulation results and comparisons show the effectiveness of the proposed algorithm.Secondly, for the no-wait flow-shop scheduling problems with sequence-dependent setup times and release dates under the total weighted earliness/tardiness criterion, we extend the above speed-up solution evaluation method to this problem according to it structural properties and also construct an interchange-based speed-up local search by using sub-neighborhood decomposition strategy and so-called "first move" strategy, and then we combine DE with the local search to present an efficient hybrid DE. Simulation results and comparisons demonstrate the efficiency and robustness of the presented algorithm.Thirdly, for the job-shop scheduling problems under the makespan criterion, we utilize active decode scheme to reduce the search space and combine an existing discrete DE with a small but effective local search to form an effective hybrid discrete DE. Simulation results manifest the necessity of the combination and the effectiveness of the algorithm.No-wait flow-shop scheduling with sequence-dependent setup times and release dates of the process industry had no scheduling algorithm based on differential evolution algorithm, This paper was focused on the kind of problem to study how to design effective scheduling algorithm based on hybrid differential evolution algorithm, At the same time, discrete differential evolution algorithm for JSP is very scarce, This paper discussed how to fuse the local search and discrete differential evolution algorithm. So the research has important academic and engineering, and has a certain innovation.