求解第Ⅰ类装配线平衡问题的离散粒子群优化算法

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