基于改进PSO的大规模序列Flowshop调度算法研究的综述报告.docx

基于改进PSO的大规模序列Flowshop调度算法研究的综述报告
序言
大规模序列Flowshop调度问题是指在一个由m台具有相同加工能力的机器所组成的n个作业的数值处理和排序问题。该问题在很多工业领域中都有应用。在Flowshop调度问题中，流水线不断地从一台机器到另一台机器来处理各个作业，每台机器每次只能处理一项工作，每个作业都需要按照一定的先后顺序被加工。确定加工序列和排程，是Flowshop调度问题中的难点。针对该问题，科学家们采用了不同的算法，其中改进PSO算法是一种有效的算法技术。本文旨在对基于改进PSO算法的大规模序列Flowshop调度算法进行综述。
改进PSO算法
PSO（ParticleSwarmOptimization）算法是一种新型的优化算法，仿照鸟群觅食的行为过程而得出。该算法包含一个随机初始化的粒子群，每个粒子表示待求解点的一维坐标，同时每个粒子还具有速度和适应度值。在迭代过程中，每个粒子根据自己的历史最优和全局最优学习并改变自己的状态，用于搜索问题的最优解。
改进PSO算法是在传统PSO算法的基础上进行改进。主要思路是增加算法的多样性，防止算法出现过早收敛等问题。改进PSO算法主要由以下几个方面进行改进。
（1）引入惯性权重：在迭代的过程中，向量的惯性似乎是调整粒子的移动方向非常重要的因素之一。在迭代初期时，保持向量的惯性较大，可以在搜索空间中获得更多的解。但是，随着速度的不断增加，向量的惯性应当逐渐减少，以帮助粒子越来越接近全局最优解。每个粒子的速度更新公式为：
$$V_{i,j}(t+1)=wV_{i,j}(t)+c_1r_1[Pbest_{i,j}(t)-X_{i,j}(t)]+c_2r_2[Gbest_j(t)-X_{i,j}(t)]$$
其中，V表示粒子的速度矢量，X表示粒子的位置矢量，Pbest表示粒子的最佳位置矢量，Gbest表示所有粒子的最佳位置矢量。
（2）采用随机搜索策略：改进PSO算法中，每个粒子在学习邻域时，根据一定的概率随机选取某些粒子进行学习。
（3）舍去较差粒子：在每轮迭代中，选择一部分表现好的粒子，舍去较差的粒子。
改进PSO算法的改进增加了算法的多样性和全局搜索能力，更适用于解决复杂的优化问题。
基于改进PSO的序列Flowshop调度问题
序列Flowshop调度问题是指在一个由m台具有相同加工能力的机器所组成的n个作业的数值处理和排序问题。在这种情况下，每项工作必须经过m个处理阶段，以满足整个生产流程的要求。在Flowshop调度问题中，流水线不断地从一台机器到另一台机器来处理各个作业，每台机器每次只能处理一项工作，每个作业都需要按照一定的先后顺序被加工。确定加工序列和排程，是Flowshop调度问题中的难点。
基于改进PSO算法的序列Flowshop调度算法，使用了启发式算法求解方法。该算法的基本思想是将问题分成两部分，分别是匹配生产和机器排序。具体流程如下：
（1）初始化粒子群，每个粒子保留着工件的一种处理序列;
（2）评价初始化的粒子群，得到适应值;
（3）选取全局最优的适应粒子作为全局最优粒子；
（4）每个粒子按照改进PSO算法进行学习；
（5）评估每个学习后的粒子的适应度，更新全局最优粒子；
（6）不断重复步骤(4)-(5)直到迭代结束。
当基于改进PSO的序列Flowshop调度算法得到最优解时，在机器上按照排序得到生产计划，即可完成整个序列Flowshop调度问题。
小结
序列Flowshop调度问题是一个典型的组合优化问题，是许多工业领域所需要处理的问题。解决该问题需要采用一种高效的算法来求解最优解。改进PSO算法具有较好的全局搜索解空间和多样性，较适用于解决复杂的优化问题。因此，基于改进PSO算法的序列Flowshop调度算法是一种非常有效的解决方案。