装配作业车间调度的免疫粒子群算法实现

Implementation of Immune Particle Swarm Optimization Algorithm for Assembly Job Shop Scheduling

装配作业车间调度问题(AJSSP)是一类重要的调度问题,由于其复杂性高和求解时间长,因此寻找高效的求解算法具有重要的意义。针对多层装配工序的作业车间调度问题给出3种求解方案:粒子群算法(PSO)、基于浓度抑制的免疫粒子群算法(IPSO)和采用“精英替代”策略的粒子群算法(EIPSO),并通过大量计算验证3种算法的优劣性。结果表明,IPSO优于PSO和EIPSO。IPSO由于免疫算法的加入,避免了PSO算法中高浓度粒子的过度复制和过早收敛,提高了全局搜索能力,能更好地求解装配作业车间调度问题。

Assembly job shop scheduling problem (AJSSP) is an important form of scheduling problem. It is important to find efficient solution algorithms because of its complexity and long solution time consumption. This paper proposes three algorithms for AJSSP: particle swarm optimization (PSO), immune particle swarm optimization (IPSO) based on concentration inhibition concept and IPSO incorporating elite preserving technique (EIPSO), then verify the advantages and disadvantages of the three algorithms through a large number of solution examples. The results show that IPSO is superior to PSO and EIPSO. Due to the addition of immune algorithm, IPSO avoids excessive replication and premature convergence of high-concentration particles in PSO algorithm, improves global search ability, and can better solve assembly job shop scheduling problems.