关键词: 混合流水车间调度问题, 改进粒子群算法, 新的NEH启发式算法, 激素调节机制, 随机拓扑结构

Abstract: For solving the Hybrid Flow-Shop Scheduling Problem with Identical Parallel Machine (HFSP-IPM),an Improved Particle Swarm Optimization (IPSO) algorithm was proposed.A mathematical model was established to minimize the makespan.Then the encoding and decoding method was designed based on permutation,and a New Nawaz-Enscore-Ham (NNEH) heuristic algorithm was proposed to improve the initial population.The speed update formula was improved based on the hormone regulation mechanism and correlation coefficient method.A random topological structure was used to replace the population optimal position with the variable neighborhood optimal position.Two crossover operators and three mutation operators were randomly used to enhance the global optimization ability of the algorithm.The results of two comparative experiments showed that NNEH heuristic algorithm generated a better initial population,and the improved speed update formula could enhance the search quality of the algorithm.The result of benchmark experiment verified that IPSO algorithm had superior performance in solving the HFSP.

Key words: hybrid flow-shop scheduling problem, improved particle swarm optimization algorithm, new Nawaz-Enscore-Ham heuristic algorithm, hormone regulation mechanism, random topological structure