基于IWD算法的多目标混合品种装配线平衡问题 .pdfVIP

基于IWD算法的多目标混合品种装配线平衡问题

李明富;张玉彦;周后明

【摘要】为简化混合装配平衡问题的求解,进而提高装配线的生产效率,在兼顾产品

切换引起负荷波动的基础上,综合工作站数、工作负荷平衡和任务关联度三个优化

目标,提出一种求解多目标混合品种装配线平衡问题的改进型IWD(intelligent

waterdrop)算法.对IWD算法的节点转移规则进行改进,加入最大概率引导规则和

随机有哪些信誉好的足球投注网站规则;采用Pareto占优的方式对解进行分层以获得前沿解集,并根据分层

结果给每个粒子提供一个启发值,依据启发值实施全局更新,增加算法的全局有哪些信誉好的足球投注网站能

力;通过测试各种标准问题,验证了改进型IWD算法比遗传算法的求解速度更快、

效率更高.

【期刊名称】《计算机集成制造系统》

【年(卷),期】2016(022)004

【总页数】9页(P965-973)

【关键词】混合品种装配线;IWD算法;Pareto占优;任务关联度

【作者】李明富;张玉彦;周后明

【作者单位】湘潭大学机械工程学院,湖南湘潭411105;湘潭大学数学与计算科学

学院科学工程计算与数值仿真湖南省重点实验室,湖南湘潭411105;湘潭大学机械

工程学院,湖南湘潭411105;湘潭大学机械工程学院,湖南湘潭411105

【正文语种】中文

【中图分类】TP24;TP29;TP39

近年来，混合品种装配线逐渐在汽车、电子、服装等制造业中得到广泛应用，而混

合品种装配线平衡问题(Mixed-ModelAssemblyLineBalancingProblem,

MMALBP)是企业在设计阶段需要解决的基本问题之一，其平衡的微小改进可带来

经济上的显著收益[1]。MMALBP包括三类问题：第Ⅰ类问题是给定生产节拍，优

化工作站数；第Ⅱ类问题是给定工作站数，优化生产节拍；第Ⅲ类问题是最小化装

配线的工作负荷平衡。

第Ⅰ类和第Ⅲ类问题需要在装配线建造前解决，解决方案直接关系到装配线的可行

性及产品的制造成本，因此较好地解决这两类问题具有非常重要的理论意义和经济

价值。关于这方面的研究主要集中在建立数学模型和改进计算方法两方面。由于实

际生产过程日益复杂，在建立数学模型时需要考虑的影响因素逐渐多元化(如负荷

平衡[2]、设备成本[3]、装配线调整引起的再平衡成本[4]等)，多个影响因素增加

了MMALBP的难度，计算方法需要随之改进。目前，装配线平衡问题计算方法分

为整数规划法和启发式方法两大类。整数规划法包括枚举法、动态规划法、分枝定

界法等[5],启发式方法包括模拟退火算法[6]、粒子群算法[7-8]、遗传算法[9]等。

然而，在规模增大时MMALBP会出现组合爆炸问题，整数规划法在有限时间内不

能获得满意解，启发式算法在有限时间内获得的解具有不确定性，因此如何更高效

地解决MMALBP仍然是该领域的研究热点。

IWD(intelligentwaterdrop)算法是近年提出的一种新算法[10]。基本IWD算法

是针对离散问题提出的，在求解整数规划等离散问题时，IWD算法无需离散化操

作。IWD算法与经典的离散蚁群算法的主要差异在于前者的粒子具有速度属性，

同时考虑了粒子速度变化对全局寻优能力的影响。因此，IWD算法比蚁群算法具

有更好的收敛速率和求解效果[11]。在提出后的几年时间里，IWD算法已经在一

些整数规划问题的求解上获得成功应用，如N皇后问题和旅行商问题[11]、车间

作业调度问题[12]等。这些研究表明，IWD算法在解决NP难度整数规划问题上

具有巨大潜力。

为实现装配线的最大效率和厂房利用率，MMALBP求解中常包含多个优化目标，

如工作站数、设备利用率和工作负荷平衡等。本文在兼顾产品切换引起负荷变化的

基础上，引入任务关联度最强这一目标，结合最小化工作负荷平衡和工作站数来构

建MMALBP的目标函数，但是多目标的引入将使该问题进一步复杂化。为简化多

目标MMALBP，最常用的方法是将各个目标函数进行加权[13-15]，形成一个评

价函数，这种方法的弊端是很难确定权重，文献[16]对多种权重值选取方法进行了

研究，发现不同权重值对装配线的平衡率影响较大。此外，很多目标函数是相互冲

突与矛盾的，当将这类目标进行加权时，权重值的设定显得尤为重要，通常需要专

家评判和反复校