改进粒子群算法在车间作业调度中的研究

Study and Application of an Improved Particle Swarm Optimization in Job-Shop Scheduling Problem

车间作业调度(JSP)是典型的NP难题,传统求解方法都有各自的特色和不足。免疫系统强大的信息处理能力为人工免疫应用提供了丰富的暗示,因此,免疫算法被提出,并逐渐应用于许多工程实际。针对车间作业调度这个优化问题的难处理性,提出了基于免疫粒子群算法(IPA)的JSP求解方法。在该求解方法中,结合免疫原理和粒子群算法应用于JSP的算法流程;算法采用基于操作的编码方式;依据接种疫苗和变异、免疫选择的机制来设计算子。并通过仿真,证明了IPA算法在JSP中的有效性。

The job-shop scheduling problem （JSP） is NP-hard. Traditional algorithms have their features and disadvantages. The powerful system processing capabilities of the immune system provide rich metaphors for its artificial counterpart. As a result, immune algorithm has emerged, and gradually been applied to many engineering practices. Due to the stubborn nature of the JSP, a method based on immune particle swarm algorithm （IPA） is initially brought forward to solve JSP. In this method, the IPA flow structure is presented via combining the immune theory and the particle swarm algorithm. The encoding scheme based on processes. And operator is designed according to vaccination, variation and immunity selectiveness. In the end, the simulation results show that the IPA algorithm has good performance in job-shop scheduling problems.