Research on the scheduling problem of partially re-entrant mixed assembly workshop based on IGPSO
R. Meng, M. Xiao, Y. Zhu, Z. Wu, S. Deng, Z. Wang
a College of Mechanical&Power Engineering, China Three Gorges University, Yichang, China;
b Yichang Key Laboratory of Robotics and Intelligent Systems, China Three Gorges University, Yichang, China;
c Intelligent Manufacturing Innovation Technology Center of China Three Gorges University, Yichang, China
针对部分重入混合装配车间中并行单元需处理两个以上工序且重入机器增加任务分配复杂性的调度问题，本文提出一种改进的遗传粒子群优化算法（IGPSO）。以最小化最大完工时间为优化目标，建立相应调度数学模型，设计整数编码与解码方法以表达同机多工序调度的可行方案。算法利用粒子群优化获得优质初始种群，加速遗传优化的收敛速度。通过改进后的混合装配调度基准案例进行实验验证，结果表明所建立的数学模型与所提算法能有效求解部分重入混合流水车间调度问题，改进策略可显著提高解的质量，验证了模型的可行性与算法的优越性。
混合流水车间调度问题具有流水车间与柔性生产线的特点，广泛存在于玻璃、纺织、造纸及钢铁制造等领域，已被证明为NP难问题。现有研究多假定每个工件依次通过各阶段的并行机，但在实际生产中，工件的多个工序会进入同一并行单元加工，即工件会重入该并行单元。合理调度工件加工顺序并设计有效的设备分配方案，可显著提升生产效率并缓解缓冲区压力。近年来，针对重入调度问题已有不少研究，但多数聚焦于全部设备的重入情形，对部分工序重入同一并行单元的研究较少。为此，本文研究部分重入混合流水车间调度问题，结合粒子群优化收敛快与遗传算法全局优化能力强的优点，设计改进的遗传粒子群算法（IGPSO），以快速获得更优的调度方案。
2.1 问题描述
存在n个工件，每个工件需经历m道工序（对应m个阶段），每个阶段有若干并行机可供加工。其中，有两个不连续的加工阶段使用同一并行单元进行加工。调度任务为合理安排各工件在各阶段机器上的加工顺序，使得总加工的最大完工时间最小。
2.2 问题假设
工件无优先级差异；加工一旦开始不可中断；每道工序只能在一台机器上加工；每台机器同一时刻只能加工一个工件；零时刻所有机器与工件均可用；相邻工序间的运输与准备时间包含在加工时间内；缓存区容量无限制。
2.3 符号定义
定义了工件数n、工序数/阶段数m、机器索引及决策变量（如工件前后继关系变量）等。
2.4 数学模型
以最小化最大完工时间为优化目标。约束条件包括：同一工序所有机器上每个工件只有一个紧前工件；每个工件只能作为另一工件的紧前工序；紧前与紧后工件数量相等；同一工件自身无紧前紧后关系；工件在当前机器上的完工时间与前后工序完工时间的关系；相邻工序间的完工时间约束；初始准备时间；非负性；目标函数不小于最终最大完工时间。
3.1 编码与解码
采用整数编码，编码长度为2n×m。通过示例说明：工件编码中每个元素对应工件编号，出现次数等于工序数加重入次数；机器编码中每个元素表示当前工序所选用机器编号。解码是编码的逆过程。
3.2 适应度计算
以最大完工时间作为适应度评价指标。
3.3 粒子群优化
采用标准PSO进行初步搜索，速度与位置更新公式包含惯性权重、个体认知与社会认知项。对出现的非法解，通过取整、丢弃不合理值并按照编码规则补全空缺以得到合法编码。
3.4 遗传算法优化
采用精英保留策略，避免最优个体丢失。选择操作使用轮盘赌策略；交叉操作采用两点交叉，并对重复基因按匹配关系修正；变异操作采用插入变异。
3.5 算法流程
初始化参数，随机生成初始种群，计算适应度，利用PSO初步搜索得到优化种群，然后进行选择、交叉、变异，按精英策略更新种群，迭代直至达到最大代数，输出最优调度方案。
4.1 算法对比
选取6个基准实例（其中两个工序共用同一并行单元），将IGPSO与GA、PSO对比。结果表明，在5×6、7×7等不同规模下，IGPSO得到的最大完工时间均优于GA和PSO。此外，在10个单峰与多峰基准函数测试中，IGPSO在9个函数上排名第一，表现优于PSO、GA、模拟退火、人工蜂群等算法，显示出优异的收敛精度与抗局部最优能力。
4.2 收敛性分析
收敛曲线显示，IGPSO在大多数测试函数上比对比算法更快、更准确地收敛到最优值。尤其在单峰函数F1-F5及多峰函数F8-F10上，收敛速度与精度显著提升，且在迭代后期能持续优化解，证明了其高效全局搜索能力与稳定性。
4.3 实例应用
选取某机械加工车间10种工件、7道工序（第2与第4工序共用并行单元）的实际生产数据进行仿真测试。IGPSO运行10次得到的最佳最大完工时间为1163，平均比GA短约5.2%，比PSO短约4.8%。调度甘特图清晰展示了工件重入并行单元的工序排序与机器分配，验证了算法对实际问题的有效性。
本文建立了考虑非连续工序在同一并行单元上加工的部分重入混合流水车间调度数学模型，并设计了IGPSO算法。该算法融合PSO快速收敛与GA全局搜索优势，通过PSO初步搜索获得优质初始种群，进而采用精英保留、两点交叉与插入变异等策略，有效提升了求解质量。实验证明，IGPSO在不同规模基准测试与实际生产数据中均优于传统GA和PSO，能够高效解决部分重入混合装配车间调度问题。
