基于一维粒子群算法获得零件加工最优调度方案的方法

摘要

基于一维粒子群算法获得零件加工最优调度方案的方法，具体按照以下步骤实施：步骤1：对柔性车间生产调度的问题进行数学符号的形式化描述，并确定优化目标的评定指标；步骤2：建立综合优化目标函数F；步骤3：建立调度优化过程的约束条件；步骤4：设计基于启发式规则的一维编码方式粒子群算法；步骤5：进行迭代运算，输出最优粒子，对其进行解码作为调度方案的最终结果。本发明在满足资源约束与工序约束等条件下，以制造期、机床总负荷和单机最大负荷为综合优化目标，采用一维编码方式的粒子群算法可以迅速获得零件加工的最优调度方案；加入完工时间最早的启发式规则，加速了综合目标的收敛。

主权项

基于一维粒子群算法获得零件加工最优调度方案的方法，其特征在于，以离散型柔性制造车间进行多工件多工艺路线加工为应用对象，具体按照以下步骤实施：步骤1：对柔性车间生产调度的问题进行数学符号的形式化描述，并确定优化目标的评定指标；步骤2：建立综合优化目标函数F；步骤3：建立调度优化过程的约束条件；步骤4：设计基于启发式规则的一维编码方式粒子群算法，具体为：4.1)首先定义如下变量：N——粒子种群规模；d——粒子编号，d＝1,...,N；g——当前进化代数；g_max——进化总代数；——第g代粒子d的个体极值点；gbest^g——第g代的全局极值点；——第g代粒子d的飞行速度；——第g代粒子d的位置rand()——服从U[0,1]的随机数；ω——粒子飞行惯性系数，0.4≤ω≤0.9；c₁、c₂——学习系数；r——未完工工件数目，r≤n；j_end_ij——工序O_ij的完工时间；m_end_kl——机床k加工第l道工序的完工时间；粒子在优化过程中会产生两个极值，一个是粒子飞行经过的最好位置，称为个体极值点另一个是所有粒子目前找到的最好位置，称为全局极值点gbest^g；在优化过程中，粒子不断向两个极值点“学习”，并且保留一定的原飞行方向，逐步向最优位置逼近；粒子在飞行过程中速度和位置的计算公式如下：速度计算公式：$v_d^{g+1}=\omega *v_d^g+c_1*rand\left(\right)*({\mathrm{pbest}}_d^g-x_d^g)+c_2*rand\left(\right)*({\mathrm{gbest}}_d^g-x_d^g)$位置计算公式：$x_d^{g+1}=x_d^g+v_d^{g+1};$4.2)粒子编码和解码编码时，设定粒子的每个分量表示一个选定工序，总工序数目决定粒子编码长度，使用rand()生成粒子位置、速度的各分量，形成初始粒子种群及初始速度种群；解码时，假设此时未完工工件数量为r个，且这r个工件按编号从小到大排列，按等概率挑选工件；粒子各分量视为概率p∈(0,1]；设变量q∈{1,2,...,r}，依次挑选q值，当p∈((q‑1)/r,q/r]时，选择剩余r个工件中的第q个进行加工；变量u_i表示工件i被挑中的次数，亦即工件i的第u_i个工序；若u_i等于工件i工序总数，表示该工件加工完毕，未完工工件数目r＝r‑1；如此遍历粒子的每一个分量，完成解码过程；4.3)设计启发式规则设工序O_ij可选的加工机床集合M_ij，集合中机床M_k已完成l道工序的加工任务，完工时间为m_end_kl；工序O_i(j‑1)完工时间为j_end_i(j‑1)，则工序O_ij的在机床M_k上的预完工时间C_ijk＝max(m_end_kl,j_end_i(j‑1))+t_ijk；遍历集合M_ij，选择C_ijk最小的机床M_k′作为O_ij的加工机床，则最终O_ij的开工时间为S_ijk′＝max(m_end_k′l,j_end_i(j‑1))+t_ijk′，完工时间C_ijk′＝S_ijk′+t_ijk′；4.4)设计算法流程粒子群算法的操作步骤如下，第1步：生成种群规模为N的初始粒子群，并随机生成粒子初始位置、速度，令g＝1，d＝1；第2步：对第g代中的粒子d进行解码，根据启发式规则选定机床，计算该粒子的适应度值(目标函数)F；第3步：判断粒子d的适应度值F是否小于个体极值和全局极值gbest^g，如果是则更新和gbest^g值为F；第4步：如果d<N则d＝d+1并转入第2步，否则g＝g+1并执行第5步；第5步：更新粒子速度和粒子位置并限制粒子位置在[0,1]区间；第6步：如果g＜g_max，是则转入第2步，否则找出最优粒子进行解码；步骤5：进行迭代运算，输出最优粒子，对其进行解码作为调度方案的最终结果。