免疫粒子群优化算法在车间作业调度中的应用

Application of immune particle swarm optimization to job-shop scheduling problem

针对标准粒子群优化(PSO)算法在迭代过程中容易出现粒子过早收敛从而降低其寻优能力的问题,分析了粒子在更新过程中早熟的原因,通过引入免疫系统的抗体浓度选择机制,构造了一种基于免疫机制的粒子群优化算法模型,并给出了免疫粒子群优化(IPSO)算法在车间作业调度问题(JSP)中的应用.抗体浓度选择机制使得粒子在更新迭代过程中保持了多样性,从而克服了过早收敛的缺陷.对43个JSP标准测试案例的仿真结果表明,与其他算法相比,IPSO算法能够获得更优的结果,求解时间更短,从而验证了免疫机制对算法寻优能力的改善.最后给出了LA36问题的调度结果的甘特图.

During the iterative process of standard particle swarm optimization （PSO）, the premature con- vergence of particles decreases the algorithm＇s searching ability. Through analyzing the reason of particle premature convergence during the renewal process, by introducing the selection strategy based on antibody density, an immunity based PSO model was proposed, and its application to job-shop scheduling problem （JSP） was given. The selection strategy based on antibody density makes the particles of immune particle swarm optimization （IPSO） maintain the diversity during the iterative process, thus overcome the defect of premature convergence. Simulation for 43 benchmark problem of JSP indicates that compared with the exiting algorithms, IPSO gets better result within shorter period, thus certify the improvement of the algorithm＇s searching ability by immunity mechanism. The Gantt chart of scheduling result of LA36 problem was finally given.