Research On Intelligent Optimization Algorithm With Flow-shop Scheduling

Flow-shop scheduling problem is widespread in the modern manufacture systems and flow industry processings, and has been proven to be a classical NP-hard problem. Generally, it involved variable models and performance criterias, thus can decrease the scheduling costs significantly and improve the core-competitiveness by applying optimization for the criteria. Therefore, the research on the scheduling problem is important on both the theory and practice. Optimization algorithms provide the way for solving the problem currently, and obtain the good results. Therefore, based on these algorithms, this paper makes research on three kinds of flow-shop scheduling model. The principal research aims to the following aspects:(1) An improved genetic algorithm is proposed for multi-objective of permutation flow-shop scheduling problem to optimize the makespan and total flow time. In order to keep the diversity of the population, the initial population is generated by combining heuristic algorithm and random algorithm in the proposed algorithm. The procedure of evolution is completed with selection, crossover, mutation operation and update strategy. When population evolutionary stagnated, the re-initialization mechanism is introduced to restore diversity. In addition, a variable neighborhood search algorithms is designed to accelerate population convergence and jump out of local optimum. Compared with several other optimization algorithms through experiment on the benchmarks, the results show that the proposed algorithm in both solution quality and stability is superior to other algorithms.(2) A co-evolutionary quantum differential algorithm is proposed for the blocking flow-shop scheduling problem to minimize the makespan. The proposed algorithm combines quantum evolutionary algorithm with differential evolutionary algorithm, and a novel quantum rotating gate is designed to control the evolutionary trend and increase the diversity of population. An effective co-evolutionary strategy has been also developed to enhance the global search ability of algorithm and to further improve the solution quality. Based on the benchmark instances, and compared with the current optimal algorithms, the results show that the preformance of proposed algorithm is effective and can be applied for the large scale blocking flow-shop.(3) A quantum-inspired glowworm optimization algorithm based on local neighborhood search is developed for solving the no-wait flow-shop scheduling problem with total flow time criterion. Based on the sum processing time and standard deviation of jobs on-machine, an unscheduled job sequence is constructed and initially optimized to obtain a better one by basic neighborhood search algorithm. Then, a local neighborhood search algorithm is proposed to accelerate the optimization and improve the quality of current solution. Afterwards, the basic quantum-inspired evolutionary algorithm and glowwarm algorithm are introduced and a more efficient algorithm by combining them is proposed. Besides, in order to enhance the efficiency of algorithm, the variation of neighborhood structure is evaluated by objective increment method, meanwhile, the neighborhood scope is partially searched in each iterative solution. The computational results show that the proposed algorithm is better than other algorithms both in solution quality and robustness.