改进粒子群算法在柔性作业加工时间问题研究_曲鹏举.pdf

第4 1卷 第1期2 0 2 3年1月MA CH I N E R Y&E L E C T R ON I C SV o l.4 1N o.1J a n.2 0 2 3收稿日期:2 0 2 2 0 8 0 2基金项目:贵州省教育厅青年科技人才成长项目(黔教合KY字2 0 1 82 4 3)作者简介:曲鹏举(1 9 8 8-),男,河南林州人,硕士,讲师,研究方向为先进制造模式与制造信息系统。改进粒子群算法在柔性作业加工时间问题研究曲鹏举(贵州理工学院工程训练中心,贵州 贵阳5 5 0 0 0 3)摘 要:为了减少柔性作业加工时长,在柔性作业加工问题中,提出一种改进粒子群算法(P S O)。该算法以最小加工时间为目标函数,惯性权重幂函数自适应调节,随机数采用贝塔分布进行改进,选取K a c e m算例进行验证,通过对比P S O算法与标准粒子群算法(P S O)、余弦惯性权重改进粒子群算法(C P S O)的优化结果,P S O算法加工时间均较低。实验结果表明,P S O算法在减少柔性作业加工时间问题上的有效性。关键词:粒子群算法;幂函数自适应权重;贝塔分布;最小加工时间中图分类号:T P 3 0 1;TH 1 6 文献标志码:A 文章编号:1 0 0 1 2 2 5 7(2 0 2 3)0 1 0 0 0 3 0 4R e s e a r c ho nP r o c e s s i n gT i m eP r o b l e mo f I m p r o v e dP a r t i c l eS w a r mO p t i m i z a t i o n i nF l e x i b l eJ o bQ UP e n g j u(E n g i n e e r i n gT r a i n i n gC e n t e r,G u i z h o uI n s t i t u t eo fT e c h n o l o g y,G u i y a n g5 5 0 0 0 3,C h i n a)A b s t r a c t:I no r d e r t or e d u c e t h ep r o c e s s i n gt i m eo f t h ef l e x i b l e j o b,a ni m p r o v e dp a r t i c l es w a r ma l g o-r i t h m(P S O)i sp r o p o s e di nt h es t u d yo f t h ef l e x i b l e j o bp r o c e s s i n gp r o b l e m,t h em i n i m u mp r o c e s s i n gt i m e i sd e s i g n e da s t h ea l g o r i t h mo b j e c t i v e f u n c t i o n,t h e i n e r t i aw e i g h tp o w e r f u n c t i o ni sa d a p t i v e l ya d j u s-t e d,t h er a n d o mn u m b e r i s i m p r o v e db yb e t ad i s t r i b u t i o n.T h eK a c e me x a m p l e i ss e l e c t e df o rv e r i f i c a t i o n.B yc o m p a r i n gt h eo p t i m i z a t i o nr e s u l t so fP S Oa l g o r i t h m w i t hs t a n d a r dp a r t i c l es w a r mo p t i m i z a t i o n(P S O)a n dc o s i n e i n e r t i aw e i g h t i m p r o v e dp a r t i c l es w a r mo p t i m i z a t i o n(C P S O),t h ep r o c e s s i n gt i m eo fP S Oa l g o r i t h mi s l o w e r.T h e e x p e r i m e n t a l r e s u l t s v e r i f y t h e e f f e c t i v e n e s s o f t h eP S Oa l g o r i t h mi n r e d u c-i n gt h ep r o c e s s i n gt i m eo f f l e x i b l e j o b s.K e yw o r d s:p a r t i c l es w a r mo p t i m i z a t i o n;c o s i n ep o w e r f u n c t i o na d a p t i v ew e i g h t;b e t ad i s t r i b u t i o n;m i n i-m u mp r o c e s s i n gt i m e0 引言近年来,柔性作业加工已经在微电子、小批量零件等领域得到广泛应用,柔性作业车间生产问题(f l e x i b l e j o b s h o pp r o c e s s i n gp r o b l e m,F J P P)也成为了制造领域重点研究的问题之一,柔性作业加工时间问题就是其中的关键。粒子群算法由于参数少,操作简单,已经广泛应用于柔性加工问题中。顾幸生等1对柔性作业车间调度问题中的多个性能评价指标进行研究后,提出了改进博弈粒子群算法;I s m a y i l o v等2为解决工作流多目标优化问题,提出了一种基于预测的动态多目标进化算法;马学森等3针对传统粒子群算法求解云计算多目标任务调度的收敛速度慢、精度低的缺陷,提出一种优化多目标任务调度粒子群算法32 0 2 3(1)(MO T S P S O);崔航浩等4针对以最小化最大完工时间为目标的MR CF J S P,提出了一种带随机网络的多种群粒子群优化算法;张闻强等5针对多目标F J S P求解过程复杂、算法易陷入局部最优的问题,提出了一种基于多区域采样策略的混合粒子群优化算法;张立果等6针对大多数算法求解多目标柔性作业车间调度问题时,所存在的稳定性差、搜索深度不够、无法对多目标中单一目标进行深入搜索的问题,对传统遗传算法做出改进,提出了一种求解多目标问题的双层遗传算法;D o n g等7为解决传统粒子群优化(P S O)中的早熟收敛问题,提出了基 于 对 立 策 略 的 的 自 适 应 变 异 粒 子 群 优 化(AMO P S O);胡志刚等8针对有效解决云环境中任务分配问题从而有效降低能耗,提出了一种改进的粒子群优化算法。贝塔分布作为统计学上的概率分布,在粒子群算法的优化问题中的应用也逐渐增加。胡棠清等9为解决粒子群优化算法中存在的早熟收敛、易陷入局部寻优等问题,提出一种对惯性权重的非线性改进策略,构造了一种基于指数函数的惯性权重,并加入服从贝塔分布的随机调整数,以实现对 其 动 态 调 整;周 蓉 等1 0针 对 粒 子 群 算 法(P S O)易早熟收敛、逃离局部最优能力差、精度低等缺点,提出一种基于灰狼优化的反向学习粒子群算法,该算法非最优粒子采用贝塔分布,提高其搜索效率和开采性能;黄洋等1 1提出了一种动态调整 惯 性 权 重 的 简 化 均 值 粒 子 群 优 化 算 法(D S MP S O),该算法构造了一种基于余弦函数的惯性权重,并加入服从贝塔分布的随机调整策略,以实现对惯性权重的动态调整,从而更好地平衡算法的全局和局部搜索能力;王勇亮等1 2在收敛因子和种群位置更新公式中引入三角函数和贝塔分布,提高了算法后期的收敛速度。为了减少柔性作业加工时长,本文提出一种改进粒子群算法(P S O)。1 问题描述及模型构建1.1 柔性作业加工问题模型柔性作业加工问题定义:已知有n个待加工工件,在m台可用机器设备上进行加工,每个工件有m道工序需要加工,每个工件的加工工序以及加工耗时已知,在符合柔性作业加工时间问题约束条件下,使总体加工时间最短。柔性作业加工时间问题模型描述如下:a.待加工的工件集J=J1,J2,J3,Jn,车间加工可使用机器集M=M1,M2,M3,Mm,其中最大工件数为n,最大可用机器数为m。b.每个工件加工工序不同、加工顺序固定,工序集合P=PiP1,P2,P3,Pn,i|i=1,2,3,n,Pi为编号为i的工件的所有工序,Pi j为编号为i的工件的第j个工序。c.S Ti j k、Fi j k、Ci j k分别为工件i的第j道工序在k号机器的加工起始时间、加工结束时间与加工持续时间,其中kk=1,2,3,m。d.Tk为k号机器实际运行时间,Fm a x为所有工件的全部工序完成的最后结束时间。柔性作业加工时间的优化目标是在接近实际生产的环境下,尽可能把各种机器、所有工件和所有工序做到合理分配,使Fm a x全部工序完成的最后结束时间最短,确定的加工时间目标函数为m i nFm a x=m i n m a xTk(1)1.2 柔性作业加工时间问题约束条件在全部工序加工过程中,加工可使用机器可以为任意待加工工序提供支持。根据机器加工的工艺流程以及实际加工中各项工序的完成顺序,特定的机器按照工艺流程、工艺卡片,同一时间只能进行某种工序的加工。在保证紧前工序完成之后,才能进行下一个加工时间的确立。因此,加工的约束必须满足下列条件,即:Fi j k-Fi(j-1)kCi j k 1jSi(2)Fa b k-Fi j mCa b k(3)Fi j mCi j k(4)式(2)表示所有工件的工序都需要消耗时间,必须按照特定的顺序完成;式(3)表示机器不重复占用原则,任意1台机器不能在同一时间内完成多个工序;式(4)表示加工持续时间的约束。2 改进的粒子群算法2.1 标准粒子群算法粒子群优化算法(p a r t i c l es w a r mo p t i m i z a t i o n,P S O)是一种典型的群体智能优化算法。该算法因为编程简单、参数且时间复杂度低而广泛应用于众多领域。标准的粒子群优化算法位置和速度状态属性为:4曲鹏举:改进粒子群算法在柔性作业加工时间问题研究研究与设计t+1i s=t+1i s+c1r1(pti s-xti s)+c2r2(pti s-xti s)(5)xti s=xti s+t+1i s(6)r1、r2为区间(0,1)内均匀分布的随机数;c1、c2分别为个体学习因子和群体学习因子,通常为非负常数;为惯性权重因子,直接决定了收敛的速度;i=1,2,3,n,为 粒 子 群 的 群 体 个 数;Xti=xti1,xti2,xti3,xti S,xti SLS,HS,LS、HS为搜索空间第s维的上限和下限;ti=ti1,ti2,ti3,ti ST,ti Sm i n,S,m a x,S,m i n,S、m a x,S分别为粒子在第s维上的最小和最大速度;pti=pti1,pti2,pti3,pti ST为个体最优位置,ptg=ptg1,ptg2,ptg3,ptg S为全局最优位置,其中,1sS,1iN。2.2 粒子群算法参数的改进2.2.1 粒子群算法惯性权重的改进惯性权重对粒子群算法的收敛速度及收敛质量有重要影响,为了解决标准粒子群算法求解过程中收敛性缓慢、稳定性低和易陷入局部最优等缺点,惯性权重不应该是固定值,而应该随着迭代次数的增加,前期有较大的惯性权重,加强全局寻优能力,后期有较小的惯性权重,局部寻优能力较强,所以本文提出惯性权重幂函数自适应调节方法,即(t)=m a x+m i n