关键词: 第Ⅰ类装配线平衡问题, 离散粒子群优化, 简化变邻域搜索, 排列编码

Abstract: To solve the assembly line balancing problem of type Ⅰ which contained NP-hard feature, a kind of Discrete Particle Swarm Optimization(DPSO)algorithm was proposed. In DPSO, a permutation encoding method was developed to ensure the decoding particles satisfy the precedence constrains of assembly operations. Aiming at the characteristic of permutation encoding, a position updating mechanism based on crossover operator was proposed to keep the feasibility of the particle. To improve the global optimization of DPSO, the Reduced Variable Neighborhood Search(RVNS)was incorporated into DPSO, and the best particle's neighborhood of swarm was local searched by proposed method. Thus a Hybrid Particle Swarm Optimization(HPSO)was constructed. The effectiveness of algorithms was verified by a series of tests. The computational comparison between existing Genetic Algorithms(GAs)and HPSO indicated that HPSO was superior to existing GAs with respect to the tradeoff between solution quality and computation efficiency.

Key words: assembly line balancing problem of type Ⅰ, discrete particle swarm optimization, reduced variable neighborhood search, permutation encoding