文档介绍：该【面向第二类装配线平衡问题的改进粒子群算法 肖晖 】是由【十二官】上传分享，文档一共【7】页，该文档可以免费在线阅读，需要了解更多关于【面向第二类装配线平衡问题的改进粒子群算法 肖晖 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。网络首发时间:2022-07-2910:24:05
网络首发地址:.
第卷第期湖北大学学报自然科学版
451 ()
年月
20231 JournalofHubeiUniversity(NaturalScience)
文章编号:
10002375(2023)01000000
面向第二类装配线平衡问题的改进粒子群算法
肖晖,郑巧仙
湖北大学计算机与信息工程学院湖北武汉
(,430062)
摘要:为求解第二类装配线平衡问题建立一种以最小化节拍工位负载标准差为优化目标的第二类装线平衡问题
,、
的模型根据装配线平衡问题的特点设计出一种改进的粒子群算法引入随迭代次数增加而线性递减的惯性权重防止
.,,,
粒子群算法陷入局部极值点将反向学****策略与算法相结合使算法具有更佳的搜索能力和收敛速度通过求
;PSO,PSO.
解标杆问题结果表明改进的算法与标准算法相比具备更好的求解能力最后通过对青贮机装配线为实例验
,PSOPSO,.
证算法的可行性和有效性进一步验证了本文中提出的改进算法具有很强的计算效率和求解能力
,PSO.
关键词:装配线平衡多目标优化粒子群算法局部极值反向学****br/>;;;;
中图分类号:文献标志码:DOI
A :.1000-
著录信息:肖晖郑巧仙面向第二类装配线平衡问题的改进粒子群算法湖北大学学报自然科学版
,.[J].(),2023,45(1).DOI:/
-.
XIAOH,-linebalancingproblem[J].
JournalofHubeiUniversity(NaturalScience),2023,45(1).DOI:.1000-.
Improvedparticleswarmoptimizationalgorithmforthesecondkindof
assembly-linebalancingproblem
XIAOHui,ZHENGQiaoxian
(CollegeofComputerandInformationEngineering,HubeiUniversity,Wuhan430062,China)
Abstract
:Forthesecondkindofassemblylinebalancingproblem,anassembly-linebalancingmodelis
establishedtominimizetheproductionbeatandthestandarddeviationofassemblylineworkstationload.
Accordingtothecharacteristicsofassemblylinebalancingproblem,animprovedparticleswarmoptimization
(PSO)
introducedtopreventthePSOalgorithmfromfallingintolocalextremepoints;Combiningthereverselearning
strategywithPSOalgorithm,
benchmarkproblem,theresultsshowthattheimprovedPSOalgorithmhasbettersolvingabilitythanthe
,thefeasibilityandeffectivenessofthealgorithmareverifiedbytakingthe
silageassemblylineasanexample,whichfurtherverifiesthattheimprovedPSOalgorithmproposedinthis
paperhasstrongcomputationalefficiencyandsolvingability.
Keywords
:assembly-linebalancing;Multi-ObjectiveOptimization;PSO;Localextremum;OBL
0 引言
装配线常被用于生产大批量的标准化产品在装配线上未完成产品通过连续的工位不同的工位
.,,
收稿日期
:20220528
基金项目国家自然科学基金资助
:(61803149)
作者简介肖晖男硕士生郑巧仙通信作者副教授研究方向为优化问题建模与算法设计
:(1998),,;(1978),,,,E-mail:
******@
湖北大学学报自然科学版第卷
2()45
执行不同操作最终获得完整的产品装配线平衡问题[1]又能
,.(AssemblyLineBalancingProblem,ALBP)
这样描述将存在优先关系的操作集合分配至给定数量的工位集合中并且一个操作只能分配到一个工
:,
位中每一个工位上所有操作的时间总和只能小于装配线的节拍并且还要让各个工位上的操作时间总
;,
和均匀分配在工业生产中具有非常珍贵的价值属于一类在调度优化中很值得研究的问题同
.ALBP,,
时又是难问题[2]作为离散约束优化问题[3-4]具有约束条件多可行解空间离散以及可行解
NP.,ALBP、
少等特点求解的难度较大
,.
装配线平衡问题普遍有两类第一类装配线平衡问题[5-6]在给定装配线节拍的情况下最小化工作
,:,
站数目目的是在满足一定生产率的同时尽可能少的运用工作站第一类装配线平衡问题在新建立装配
,,
线时就会存在第二类装配线平衡问题[7-9]在给定装配线工位数量的情况下使节拍最小目的是提高
;:,,
具有一定工作站数目的现有装配线的产品生产率如果利用现有装配线重新设计装配工艺时就会存在
,
第二类装配线平衡问题第二类装配线平衡问题被研究的频率是要比第一类装配线平衡问题更频繁因
.,
为市场需求每时每刻在不断变化产品的产量与品种也在频繁变化工厂需要依据有限的人员和设备调
,,
整装配线尽可能地使自己的生产水平适应不断变化的市场让工厂的生产柔性得到提高
,,.
最近的一些年来许多研究者对装线平衡问题进行了研究李明郑巧仙等针对离散多约束优化问
,.,
题可行解的存在性方面进行了分析和证明[10]在求解算法方面杜利珍王运发等根据第二类装配线平
.,,
衡问题的特点兼顾生产节拍最小和工作负荷均衡运用果蝇算法对第二类装配线平衡问题进行求
,,
解[11]麻娟刘俨后等在混合遗传算法中引入烟花算法爆炸算子中基于免疫浓度思想为装配线平衡
.,,,
问题的解决提供了一种新方法[12]
.
粒子群算法[13]因为在组合优化问题的求解方面具有很好的的收敛速度和很高的全局寻优能力等
优点常常被学者用来进行研究为了对第二类装配线平衡问题进行求解本文提出一种改进的粒子群
,.,
算法通过求解标杆问题结果表明改进的算法与标准算法相比具备更好的求解能力最后
,,PSOPSO,.
通过对青贮机装配线为实例验证算法的可行性和有效性进一步验证了本文提出的改进算法具有
,PSO
很强的计算效率和求解能力
.
1 第二类装配线平衡问题的数学模型
=i|i工位集合为J=j|j
ALBP-2{=1,2…,|I|},{=1,2…,|J|},
表示操作数量表示工位数量T表示第j个工位中所有操作时间总和装配线的生产节拍为
|I|,|J|,j.
C工作站负载标准差为L集合I中操作i的操作时间为i记P=PiiiiI为一个行
,.t.(1,2),1,2∈|I||I|
列的矩阵其中某行某列的值只能是或表示所有操作的优先关系如果操作i是操作i的直接前
,01,,12
序Pii=其余情况下Pii=iiI第二类装配线平衡问题的优化目标是最小化装配线
,(1,2)1;,(1,2)0,1,2∈.:
的节拍和工位的负载标准差
.
=否则x=该问题
ij(∈,∈)0-1,,ij1;,ij0.
的数学模型如下
:
Z=×Z+×Z
(1)
J
||
T2
(j-C)
Z=CZ∑j=1
1,2=J|(2)
|-1
xijxijiiIPii=
. jJj1·11≤jJj2·22,1,2∈,121(3)
∑1∈∑2∈
tixijCJ
iI·≤,j∈(4)
∑∈
xij=iI
J1,∈(5)
∑j∈
其中为问题的总目标Z是装配线节拍Z是装配线工位负载标准差表示操作间的
,(1);(2)1,2;(3)
优先关系当操作i是操作i的直接前序那么该操作所分配在的工位j的次序大小应小于或等于其直
,12,1
第期肖晖等面向第二类装配线平衡问题的改进粒子群算法
1,: 3
接后序操作所分配在的工位j的次序大小表示所有工位上的操作时间总和小于等于装配线节拍
2;(4);
表示对于所有操作操作要被分配至工位集合中的一个工位上并且只能分配一次
(5),,.
2 求解第二类装配线平衡问题的改进粒子群算法
(ParticleSwarmOptimization,PSO)
的算法该算法的核心思想是依据粒子群中的粒子之间的信息共享因而让整个粒子群体的运动在对问
,,
题求解过程中不断变得有序因而求解问题粒子群算法得这种对信息的共享机制可以理解成粒子之间
,.
的共生合作的关系每一个粒子都在不停搜索而且其搜索的行为同时在受到其他粒子的影响即向整
,,,
个种群目前找到的最有解学****而且不同粒子还有对自己所经历最佳位置的记忆功能它的搜索行为同
.,
时又受自身经验的引导即记录自己所找到的最优解而向这个解学****br/>,.
假设一个维空间Xi=xixixi用以表示第i个粒子的位置Vi=vivivi用以表
n,(1,2,…,n),(1,2,…,n)
示第i个粒子的速度Pbesti=pipipin表示第i个粒子的个体最优解Gbesti=gigigin
,(1,2,…,),(1,2,…,)
表示粒子群的历史最佳位置建立标准粒子群算法其中粒子速度迭代变化和位置迭代变化的数学模型
,,
如下所示
:
t+t
1
Vi=wVi+ci-Xi+ci-Xi
·1·r1·(Pbest)2·r2·(Gbest)(6)
Xt+1=Xt+Vt+1
iii(7)
t+
1
-VViV
max≤≤max(8)
中w为惯性权重表示上一次迭代更新速度对下一次迭代更新速度的影响分别
(6)(7)(8):,;c1、c2
为个体学****因子和群体学****因子和为范围内的均匀随机数V表示粒子的最大速度必须
;r1r2[0,1];max
小于这个值若粒子某一维的速度大于V则取速度为V若粒子某一维的速度小于V则取速度
,max,max;-max,
为V
-max;
,
收敛性的智能优化算法若粒子群在迭代早期就陷入局部的极值在后面的迭代也就难以跳出这个局部
.,
的极值这种情况不但大大降低粒子群求解的效率并且也大大降低粒子群发现全局最优解的概率针
,,.
对这一问题改进的粒子群算法引入一种随着迭代次数增加而线性递减的惯性权重w在搜索进行当中
,,
根据迭代次数的增加而对惯性权重w不断进行调整在粒子群算法开始的时候惯性权重w取得较大
:,
值依据迭代的不断进行惯性权重w也跟着线性变小这种策略保证粒子群算法在开始的时候粒子都
;,.
具有较大的速度步长可以有更大概率跳出局部的极值使得粒子群体可以在全局范围内探测较好的区
,,
域随着粒子群算法的不断迭代跟随变小的惯性权重w可以保证各个粒子能够在极值点附近进行精细
;,
的搜索进而使粒子群有很大的概率向全局最优解收敛增大搜寻到最优解的概率表达式如下
,,.:
wwt
w=w(max-min)·
max-t(9)
max
中w表示最大惯性权重w表示最小惯性权重t为当前迭代次数t表示最大迭代
(9):max;min;;max
次数
.
[14]提出的一种
(opposition-basedlearning,OBL)Tizhoosh
在智能群体领域中广泛运用的策略该策略的原理为根据当前的可行解求出当前可行解的反向学****br/>.:,
后的解并且在当前的可行解和反向学****后的解中间进行选择挑选出其中较好的解
,,.
定义若xab的任意实数则x的基于反向学****的数如下所示
1:∈[,],:
x′=a+b-x
(10)
定义若pxxxD之间的任意D维空间中的点为xixixi则它反向学****的解如
2:=(1,2,…,)∈[min,max],
下所示
p′=x′x′x′D
12
(,,…,)(11)
x′i=xi+xi-xi
minmax(12)
粒子方向反向学****由粒子群速度更新公式可知粒子的方向由Vpbest和gbest所决
(6),ii,i
湖北大学学报自然科学版第卷
4()45
定粒子i的V是固定的而下一次飞行的飞行方向是被pbest和gbest所影响对此提出一种粒子方向
.i,i.,
反向学****策略用策略生成决定粒子方向的pbest和gbest的反向解并与已知的的pbest和gbest
:OBLi,i
做比较在目标函数中求取适应度优先选择适应度较小的解作为下一代个体对适应度进行修改使粒
,,,,
子飞往更优的方向
.
健壮粒子反向学****当面对数量非常多的粒子个体时如果对所有个体都进行反向学****计算
,,
量巨大而且非常容易减小粒子搜索的精度因而提出一种健壮粒子反向学****模式在进行反向学****之
.:
前对当前例子群体中所有粒子求取其适应度选择其中适应度最小的粒子称之为健壮粒子仅对健壮
,,;
粒子求反向解进而引导粒子群中粒子向最优解飞行
,.
,|I|(
作数目的取值范围在之间的随机数依次排列而成的解码步骤如下
),[-,].:
在优先顺序图中寻找无紧前操作的操作将他们存入集合T中
Step1:,;
在存入集合T中所有的操作中选择优先权值最大的操作将Tchoose设置为这项操作
Step2:,,;
将操作Tchoose放入作业任务顺序集R中并在优先图上删除操作Tchoose
Step3:,;
当作业任务顺序集R中的个数为表示所有操作的数量意味着操作都被分配完了结
Step4:|I|(),,
束解码否则表示还有任务没有分配那么返回步骤继续解码
;,,1.
为更好地理解解码步骤以某装配线作业操作优先图为例进行解码如图所示
,,,1.
图某装配线操作顺序图
1
假设某粒子位置编码x
={,,,,,,}.
第次选择TTR
1:={1};choose=1;={1}.
第次选择TTR
2:={2,3,6};choose=3;={1,3}.
第次选择TTR
3:={2,5,6};choose=6;={1,3,6}.
第次选择TTR
4:={2,5};choose=2;={1,3,6,2}.
第次选择TTR
5:={4,5};choose=4;={1,3,6,2,4}.
第次选择TTR
6:={5};choose=5;={1,3,6,2,4,5}.
第次选择TTR
7:={7};choose=7;={1,3,6,2,4,5,7}.
,,
为了均匀分配操作次序序列至各个工位上进行以下操作
,:
计算理论最小节拍Csumt/|Jt其中sumt为各操作的时间总和|
Step1:=max((i)|,max(i)),(i),
J|为所有工作站数目ti为第i个作业任务的操作时间
,;
操作次序序列最大限度分配到前面的|J|个工位并且这些工位上的操作时间总和必须
Step2:-1,
小于C将剩下的还没有被分配的操作次序序列都分配到最后一个工位
,;
计算最后一个工位上的操作时间总和T若TC则C就是最小节拍退出程序而若TC
Step3:,<,,;>=,
继续进行
Step4;
计算前|J|个工位的潜能操作时间PTk|J|潜能操作时间等于已分配
Step4:-1K(=1,2,…,-1)(
至各个工位上的操作时间总和下一个工位上的第一项操作的时间令CminPTPTPTK
+),1={1,2,…,},
若TC令CTC就是最小节拍退出程序否则令CC返回继续分配
<1,=,,;=1,Step2.
第期肖晖等面向第二类装配线平衡问题的改进粒子群算法
1,: 5
3 算法分析与比较
算例1为验证改进算法的有效性选择装配线平衡问题网站
PSO,-line-balancing.
中的标杆算例进行验证用标准算法与改进的算法分别求解同一条件的标杆问题结果如
,
表所示
1.
取初始粒子数迭代次数t个体学****因子c群体学****因子c最大的速度
size=30;max=100;1=2;2=2;
V标准的惯性权重W改进的最大惯性权重w和最小惯性权重惯性权
max=;PSO=;PSOmax=
重w利用软件编程实现将各程序独立运行次取其平均值
min=;Python,20,.
表1 标杆算例对比结果
理论最小改进改进标准标准
问题任务总数任务总时间工作站数PSOPSOPSOPSO
节拍算法算法算法算法
CZ2CZ2
[15]某青贮机装
2 .
配的作业优先顺序图如图所示其中每个圆圈代表操作序号圆圈上的数字表示各操作的操作时间
2.,,,
箭头则表示操作之间的先后约束关系
.
图青贮机作业优先顺序图
2
取初始粒子数迭代次数t个体学****因子c群体学****因子c最大的速度
size=30;max=100;1=2;2=2;
V标准的惯性权重W改进的最大惯性权重w和最小惯性权重惯性权
max=;PSO=;PSOmax=
重w并且其工作站数目为利用软件编程实现将各程序独立运行次取其平
min=;,20,
均值
.
求得改进算法某次作业分配方案如表所示改进遗传算法[15]和标准算法以及本文提
出的改进算法优化性能对比如表所示为更好对比试验结果负载标准差以文献的计算
PSO3.,Z2[15]
方法为主
.
湖北大学学报自然科学版第卷
6()45
表2 装配线平衡方案
工位号作业工序作业时间
128,
22,
33,
47,
520,
65,24,
74,
88,9,11,
913,14,
1016,17,
1122,19,
1223,26,
1332,
1434,35,
1537,38,
表3 算法优化性能对比表
求解算法生产节拍负载标准差
CZ2
改进遗传算法[15]
标准算法
改进算法
4 结论
为求解第二类装配线平衡问题建立一种以最小化节拍工位负载标准差为优化目标的第二类装线
,、
平衡问题的模型设计出一种改进的粒子群算法引入随迭代次数增加而线性递减的惯性权重防止粒
.,,
子群算法陷入局部极值点将反向学****策略与算法相结合使算法具有更佳的搜索能力和收
;PSO,PSO
敛速度通过求解标杆问题结果表明改进的算法与标准算法相比具备更好的求解能力最
.,PSOPSO,.
后通过对青贮机装配线为实例验证算法的可行性和有效性进一步验证了本文提出的改进粒子群算法
,
具有很强的计算效率和求解能力
.
5 参考文献
[1]ZHENGQX,LIM,LIYX,[J].
InternationalJournalofAdvancedManufacturingTechnology,2013,66(9):1859-1870.
–
[2]LIM,TANGQH,ZHENGQX,-shapedassemblylinebalancingproblem
[J].AppliedMathematicalModeling,2017,48:423-439.
李笠约束进化算法及其应用研究综述计算机科学
[3].[J].,2021,48(4):1-13.
李智勇约束优化进化算法综述软件学报
[4].[J].,2017,28(6):1529-1546.
胡俊逸张则强张宇等求解第类装配线平衡问题的一种改进粒子群算法现代制造工程
[5],,,.Ⅰ[J].,2012(3):1-5.
毛凌翔郑永前蚁群算法求解装配线平衡第一类问题计算机系统应用
[6],.[J].,2010,19(1):140-143.
李明唐秋华郑巧仙等第类装配线平衡问题的改进规则组合算法计算机集成制造系统
[7],,,.2[J].,2015,21(1):
88-93.
李英德鲁建厦求解第二类装配线平衡问题的改进蚁群算法计算机集成制造系统
[8],.[J].,2012,18(4):754-760.
张海军闫琼张国辉离散差分进化算法求解第二类装配线平衡问题的研究科技通报
[9],,.[J].,2017,33(7):67-70.
郑巧仙李明唐秋华等多约束装配线平衡问题的可行解存在性分析计算机集成制造系统
[10],,,.[J].,2019,25(3):
619-628.
第期肖晖等面向第二类装配线平衡问题的改进粒子群算法
1,: 7
杜利珍王运发王震等基于果蝇算法的第二类装配线平衡问题中国机械工程
[11],,,.[J].,2018,29(22):2711-2715.
麻娟刘俨后楚满福等求解第类装配线平衡问题的混合遗传算法山东理工大学学报自然科学版
[12],,,.Ⅱ[J].(),
2019,33(3):55-59.
冯茜李擎全威等多目标粒子群优化算法研究综述工程科学学报
[13],,,.[J].,2021,43(6):745-753.
[14]-basedlearning:anewschemeformachineintelligence[C]//InternationalConferenceon
InternationalConferenceonComputationalIntelligenceforModelling,Control&,2005:695-701.
李明包建军袁逸萍基于改进遗传算法的多目标装配线平衡优化研究机械设计与制造
[15],,.[J].,2022(4):204-
207.
(责任编辑江津)