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

摘要： 为求解具有NP难性质的第Ⅰ类装配线平衡问题，提出一类离散粒子群优化算法。该算法中所发展的排列数编码方法使得粒子解码后总满足装配作业间先后关系约束。针对排列数编码特点，提出一种基于位置交叉算子的粒子位置更新机制，确保了更新后粒子仍为排列数。为增强该算法的全局寻优能力，将简化变邻域搜索算法嵌入该算法中，对群体最佳粒子的邻域进行局部搜索，从而构建一种混合粒子群优化算法。通过将该算法和混合粒子群优化算法用于一系列测试算例并与遗传算法结果比较，验证了算法的有效性。计算结果对比表明，离散粒子群算法引入简化变邻域搜索可明显增强全局寻优能力，就综合解的质量和计算效率而言，混合粒子群优化算法优于现有遗传算法。

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