《模糊作业时间的拆卸线平衡pareto多目标优化》由会员分享，可在线阅读，更多相关《模糊作业时间的拆卸线平衡pareto多目标优化（14页珍藏版）》请在金锄头文库上搜索。
1、模糊作业时间的拆卸线平衡 Pareto 多目标优化 汪开普 张则强 邹宾森 毛丽丽 西南交通大学机械工程学院 摘 要： 针对实际拆卸作业的复杂性, 建立了考虑模糊作业时间的多目标拆卸线平衡问题的数学模型, 提出了一种基于 Pareto 解集的多目标遗传模拟退火算法进行求解。改进了模拟退火操作的 Metropolis 准则, 使其能够求解多目标优化问题。采用拥挤距离评价非劣解的优劣, 保留了优秀个体, 并通过精英选择策略, 将非劣解作为遗传操作的个体, 引导算法向最优方向收敛。基于 25 项拆卸任务算例, 通过与现有的单目标人工蜂群算法进行对比, 验证了所提算法的有效性和优越性。最后将该算法应用
2、于某打印机拆卸线实例中, 求得 8 种可选平衡方案, 实现了求解结果的多样性。关键词： 拆卸线平衡; 模糊作业时间; 多目标优化; 遗传模拟退火算法; Pareto 解集; 作者简介：汪开普 (1991) , 男, 硕士研究生, 主要研究领域为生产线平衡与智能优化;E-mail:;作者简介：张则强 (1978) , 通讯作者, 男, 博士, 教授, 博士研究生导师, 主要研究领域为制造系统与智能优化;作者简介：邹宾森 (1990) , 男, 硕士研究生, 主要研究领域为生产线平衡与智能优化;作者简介：毛丽丽 (1992) , 女, 硕士研究生, 主要研究领域为设施布局优化。收稿日期：2016-
3、06-28基金：国家自然科学基金 (No.51205328, No.51405403) Pareto optimization for multi-objective disassembly line balancing with fuzzy operation timesWANG Kaipu ZHANG Zeqiang ZOU Binsen MAO Lili School of Mechanical Engineering, Southwest Jiaotong University; Abstract： In view of the complexity of the actual dis
4、assembly work, a mathematical model of the multi-objective disassembly line balancing problem considering fuzzy task processing time is constructed, and a Pareto based multi-objective genetic simulated annealing algorithm is proposed. An improved Metropolis criterion of simulated annealing operation
5、 is presented to make it to be applicable to multi-objective optimization problem. The crowding distance is introduced as an evaluation mechanism to filter and preserve the elite solutions, and then the elite solutions are performed the genetic operation to guide the convergence to the optimal direc
6、tion. Comparing the proposed algorithm with a single-objective artificial bee colony algorithm based on the 25-task involved disassembly case, it identifies the validity and the superiority of the proposed algorithm. Finally, the proposed algorithm is applied to a printer disassembly instance, and i
7、t acquires 8 balancing schemes and realizes the diversity of the solution results.Keyword： disassembly line balancing; fuzzy operation times; multi-objective optimization; genetic simulated annealing algorithm; Pareto set; Received： 2016-06-281 引言科技的创新推动了产品的更新换代, 加速了产品的推陈出新, 由此产生了大量的废旧机电产品, 如汽车、电脑、家
8、电等。实现废旧机电产品的回收再利用是解决当前资源与环境问题的重要出路, 也是绿色制造重要内涵。国务院于 2015年印发的中国制造 2025中强调, 要“发展循环经济, 提高资源回收利用效率, 构建绿色制造体系”, 而拆卸是实现资源回收利用的重要方式之一。通过拆卸废旧机电产品, 能够提取大量可再使用的零部件, 也可以回收大量的贵重金属、塑料等资源, 同时减轻有害物质对环境的危害。合理的拆卸任务排序能够使拆卸线趋于平衡, 提高拆卸效率, 同时降低拆卸成本。拆卸线任务排序涉及到工作站数量、工作站空闲率、成本、拆卸方向改变数等多个衡量指标, 是一种复杂的组合优化问题。为解决这一问题, 研究者对拆卸线平
9、衡问题 (Disassembly Line Balancing Problem, DLBP) 展开了探索。Gungor 等1对多目标 DLBP 进行了描述, 分析了影响 DLBP 的各种因素。Avikal 等2采用启发式算法、Altekin 等3采用数学规划法分别求解 DLBP, 均能得到精确解, 但这些方法只适用于求解小规模问题。Mc Govern 等4证明了 DLBP 是 NP 完全问题, 随着任务规模的增大, 很难在有效时间内求得最优解。亚启发式算法在求解 NP 问题时表现出良好的性能, 如遗传算法4、蚁群算法5、变邻域搜索算法6、细菌觅食算法7、强化学习算法8等方法在求解不同规模任务的
10、 DLBP 时能够得到较优解。上述方法在求解多目标 DLBP 时均是采用顺序处理各优化目标, 其本质是将多目标问题转化为单目标问题求解, 无法实现存在冲突关系的各目标间的均衡。文献9-10分别采用 Pareto 蚁群算法、Pareto 细菌觅食算法对多目标 DLBP 进行优化, 均能得到多种平衡方案, 且平衡方案兼顾了各目标间的均衡。文献1-10均是对确定作业时间下的 DLBP 展开研究, 然而在实际拆卸作业过程中, 由于废旧产品新旧程度、拆卸难易程度等因素的制约, 以及机器、作业工人等因素的影响, 都会使生产作业产生诸多不确定性11, 如零件的拆卸时间不确定性、生产节拍不确定性等。为处理不确
11、定性数据, 引入三角模糊数来表示拆卸作业时间, 模糊拆卸线平衡问题 (Fuzzy Disassembly Line Balancing Problem, FDLBP) 应运而生。由于该问题的求解难度, 研究文献甚少, 仅文献12研究了多目标 FDLBP, 通过加权法来处理存在相互冲突的各目标, 其本质还是将多目标问题转化为单目标问题求解。针对现有文献对 FDLBP 研究的不足, 有必要对该问题展开研究。遗传模拟退火算法 (Genetic Simulated Annealing Algorithm, GASA) 是求解复杂组合优化问题的有效方法, 如在求解协同制造任务分配问题13、物流网络设计问
12、题14中综合利用遗传算法较强全局搜索能力和模拟退火算法较强局部搜索能力等优点, 实现优势互补, 有效提高混合算法的搜索精度。参考已有文献, 尚未发现有关混合遗传模拟退火算法求解 FDLBP 的公开报道。鉴于现有研究的不足, 本文结合 Pareto 解集求解多目标问题的思想以及遗传算法和模拟退火算法求解组合优化问题的优势, 提出一种求解 FDLBP 的多目标Pareto 遗传模拟退火算法, 改进算法的遗传操作和模拟退火操作。通过对不同规模任务的问题进行测试对比, 验证了所提算法求解多目标 FDLBP 的性能。2 模糊拆卸线平衡问题2.1 问题描述拆卸线是实现大规模拆卸作业的最佳方式, 面对数量庞
13、大的废旧机电产品, 拆卸线越来越多地被采用。在废旧机电产品被完全拆卸的情况下, 由于受待拆卸产品新旧程度、拆卸难易程度等因素的制约, 以及机器、作业工人等因素的影响, 生产节拍和拆卸作业时间具有不确定性, 需综合考虑拆卸线工作任务分配。对于作业时间模糊的拆卸线, 每个工作站的模糊作业时间需要满足模糊节拍, 且所有任务的拆卸顺序需满足拆卸优先关系, 避免发生干涉现象。拆卸线工作任务的分配将直接决定着开启工作站数目, 而工作站作业时间的均衡性影响着生产效率;为实现经济效益最大化, 应最大限度减少拆卸成本和拆卸作业方向改变次数。2.2 目标函数针对模糊拆卸线平衡问题的特点, 建立如下多目标函数4,9
14、:(1) 最小化工作站数当拆卸生产线节拍确定时, 工作站数越少, 则相应的人员、设备、场地等需求都将减少, 也减少了拆卸线的成本。式中, M 为工作站数目。(2) 最小化工作站空闲率为提高作业效率和公平性, 应最大限度提高各个工作站间的均衡性, 减少工作站的空闲时间, 实现工作站利用率最大化。(3) 最小化拆卸成本拆卸线总的拆卸成本由各个工作站的拆卸成本之和构成, 工作站的单位时间拆卸成本定义为该工作站内拆卸任务的最大单位时间拆卸成本。应最大限度降低拆卸作业成本, 以实现生产效益最大化。式中, U n为拆卸任务 n 的单位时间拆卸成本, n 为拆卸任务编号;x mn为任务与工作站间的关系, 若
15、任务 n 被分配到工作站 m, 则 xmn=1, 否则 xmn=0。(4) 最小化拆卸方向改变次数拆卸方向过多的改变将导致非作业时间的增加, 降低拆卸作业效率。式中, r n为拆卸任务 n 的拆卸方向改变数, 若任务 n 与任务 n-1 的拆卸方向相同, 则 rn=0, 否则 rn=1。2.3 约束条件(1) 工作站数约束式中, 为拆卸任务 n 的模糊作业时间。(2) 工作站节拍约束工作站内的所有拆卸任务的模糊作业时间之和不超过工作站的模糊节拍。(3) 所有拆卸任务都必须分配到工作站中(4) 拆卸顺序必须满足拆卸优先关系3 Pareto 遗传模拟退火算法遗传模拟退火算法具有较强寻优能力, 已在
16、诸多组合优化问题13-14中得到了成功应用。本文针对模糊拆卸线平衡问题的特点, 参考文献15中的多目标处理方法, 结合 Pareto 解集思想, 提出一种求解多目标模糊拆卸线平衡问题的Pareto 遗传模拟退火算法。3.1 可行解的构造为得到多样性的初始可行解, 每次任务的选取均为随机挑选。生成初始可行解的具体步骤如下:步骤 1 从拆卸优先关系矩阵 Y 中随机挑选未分配的任务 i, 且任务 i 无紧前任务或紧前任务已分配 (即 Y 中每列全部为零的任务) , 作为当前位置处的拆卸任务。步骤 2 将与任务 i 有优先关系的约束从 Y 中删除:a1, 2, , N, 令 yia=0, yai=0。步骤 3 重复步骤 1、步骤 2, 直至所有任务分配完成, 得到的序列即为初始可行拆卸序列。3.2 模糊作业时间为处理拆卸作业中的不确定性, 采用三角模糊数表示不确定性拆卸作业时间。对于任意给定的三角模糊数 ,
